The course in kurser.ku.dk. Lecture: Mon 8-10 (A08), Tue 13-16 (S11). Exercises: Mon 10-12 (A106), Fri 10-12 (A101).
Lecturer: Michal Adamaszek |
Week | Lecture | Files | Exercises |
---|---|---|---|
6 |
Mon: Introduction and organisation. Examples of graphs. The first problem of graph theory. Definitions, standard graphs: paths, cycles, complete graphs, cubes. Vertex degrees and the handshaking lemma. Subgraphs, homomorphisms and isomorphism. Tue: (Dis)connectedness, trees, bipartite graphs. The clique and independence number. The greedy construction of an independent set. Definition of the chromatic number. |
lec1.pdf, (.tex) lec2.pdf, (.tex) |
Warm up problems: ex1.pdf. SAGE, introduction: sage1.sage. |
7 |
Mon: Chromatic number and partitioning into color classes. Lower bounds involving omega and alpha. The greedy coloring algorithm. Brooks' theorem. Tue: Mycielski's construction. The random model G(n,p). Probabilistic construction of triangle-free graphs with large chromatic number. Chromatic numbers of simple constructions: wedges, joins, cartesian product. |
lec3.pdf, (.tex) lec4.pdf, (.tex) |
Filling in a gap in Brooks' theorem. Chromatic number and other invariants: ex2.pdf. Greedy coloring algorithm: greedy.sage. |
8 |
Mon: Planar graphs. Kuratowski and Wagner's theorems (without proof). History of the 4-color theorem. Planar graphs as graphs on the sphere. Euler's formula and its applications: classification of Platonic solids and upper bounds on the number of edges. Tue: List coloring. Triangulations. Thomassen's 5-list-coloring of planar graphs. Application of planar coloring: The art gallery problem. |
lec5.pdf, (.tex) lec6.pdf, (.tex) |
Planarity. The 6-color theorem. ex3.pdf. More greedy colorings: greedy2.sage. |
9 |
Mon: Chromatic polynomial. Examples. Polynomial expansion from the inclusion-exclusion principle. The deletion-contraction rule. Basic properties of coefficients and their alternating signs. Tue: Monotonicity of coefficients of chromatic polynomials. Stanley's acyclic orientations theorem. Some remarks about chromatic roots. |
lec7.pdf, (.tex) lec8.pdf, (.tex) |
Chromatic polynomials: ex4.pdf. Chromatic polynomials in Hollywood. Fri: Solving homework 1. |
10 |
Mon: Edge coloring and edge chromatic number. Matchings. Line graphs. Simple bounds on the edge-chromatic number. Vizing's theorem (no proof). Hall's marriage theorem. Tue: Applications of Hall's theorem: Bipartite graphs are Delta(G)-edge-colorable (Koenig's theorem). Dual graphs of planar triangulations. Tait's theorem: relation between the 4-color theorem and edge coloring. |
lec9.pdf, (.tex) lec10.pdf, (.tex) |
Edge chromatic number and line graphs: ex5.pdf. We played the coloring game: ex5-game.pdf. |
11 |
Mon: Proof of Vizing's theorem and related remarks. The chromatic number of Euclidean spaces. Unit distance graphs. Chromatic number of infinite graphs via compactness. A simple 9-coloring of the plane. Tue: Lower bound (4) and upper bound (7) on the chromatic number of the plane. Moser graph. Greedy exponential upper bound on chi(R^d). Generalized cube graphs are unit distance graphs. |
lec11.pdf, (.tex) lec12.pdf, (.tex) |
Edge chromatic number, continued and Euclidean colorings: ex6.pdf. Fri: Solving homework 2. Generalized cubes in SAGE: ex7.pdf, qdu.sage. |
13 | Tue: Exponential lower bounds on chi(R^d). Independence numbers of more generalized cube graphs. Tools of linear algebra with the Odd-Town problem as warmup. | lec13.pdf, (.tex) |
Open problems. More appl. linear algebra: page 3 here. |
14 |
Mon: From coloring to topology: Sperner's lemma. Applications: Brouwer's fixed point theorem, fundamental theorem of algebra. Tue: From topology to coloring: Borsuk-Ulam's theorem. Kneser graphs and their chromatic numbers (Lovasz). |
Open problems. Around Sperner's lemma: ex8.pdf. |