Graph coloring

The course in
Lecture: Mon 8-10 (A08), Tue 13-16 (S11). Exercises: Mon 10-12 (A106), Fri 10-12 (A101).

Lecturer: Michal Adamaszek
Contact: aszek AT
Office: 04.1.18
Office hours: feel free to stop by my office or send me an e-mail


Graded assignments

Bring your solutions with you to the exercise class, or to my office, my pigeonhole, or send by e-mail. We will discuss the solutions in the Friday exercise class, so no late submissions please. Each assignment is worth 10 points.


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.

Literature pointers to some specific topics

[D] Diestel, [BM] Bondy and Murty, [B] Bollobas, [W] West
[AZ] Aigner and Ziegler Proofs from the Book
  1. Various bounds and greedy coloring: [W, 5], [BM, 14], [B, V.1], [D, 5.2]
  2. Brooks' theorem: our proof followed [D, 5.2.4.]. Another strategies are used in [BM, 14.4], [B, V.3], [W, 5.1.22]
  3. Mycielski's construction: [W, 5.2], [BM, 14.11]
  4. Triangle-free graph with large chromatic number probabilistically: [D, 11.2.2], [W, 8.5.11], [BM, 14.10], [B, VII.4]. The theorems there are more general than ours (!), substitute "triangle-free" = "girth more than 3" to reduce to our subcase.
  5. Cartesian product: [W, 5.1.9-11]
  6. List coloring: [B, V.4], [W, 8.4], [D, 5.4]
  7. Thomassen's 5-list-coloring theorem: [D, 5.4.2], [W, 8.4.32], [B, Thm. V.12], [AZ, Ch. 25]
  8. The art gallery problem: [AZ, Ch. 26], wiki
  9. Chromatic polynomials: [B, V.1], [BM, 14.7], [W, 5.3]
  10. Counting acyclic orientations: [W, 5.3.27], [BM, Ex.14.7.11], [B, Ex.V.50]
  11. Edge chromatic number and line graphs: [B, V.2], [BM, 17], [D, 5.3], [W, 7.1]
  12. Hall's marriage theorem: [B. Thm. III.3.7], [W, 3.1.11], wiki
  13. Vizing's theorem: [B, Thm. V.2.7], [D, 5.3.2], [W, 7.1.10], [BM, 17.2]
  14. A general reference for chromatic numbers of the plane and Euclidean spaces is [S]: Soifer The Mathematical Coloring Book Mathematics of Coloring and the Colorful Life of its Creators
  15. Chromatic number of the plane: [S, Ch. 2], esp. Problems 2.3,2.4,2.5. Also mentioned in [BM, Prob. 1.6.4, Prob 14.1.20], [W, Ex. 5.1.25].
  16. Compactness theorem for coloring: [S, Thm.26.1]

Planned content


For the first part of the course any standard graduate-level textbook on graph theory will be fine. For instance:
  1. Bondy, Murty, Graph theory esp. ch. 11,13,14,15,17,21
  2. Diestel, Graph theory
  3. West, Introduction to graph theory
  4. Bollobas, Modern graph theory
Information about the topological tools can be found in
  1. Kozlov, Combinatorial algebraic topology, ch. 17
And here is some light reading for long evenings:
  1. Soifer, The Mathematical Coloring Book Mathematics of Coloring and the Colorful Life of its Creators
Open problems related to graph coloring:
  1. Jensen, Toft, Graph Coloring Problems, available in our library in print and as an online resource
  2. Beineke, Wilson, Topics in chromatic graph theory, Chapter 15, available through our library as an online resource
  3. Open Problem Garden

Some open problems in graph coloring to choose from

  1. Double-critical graphs, Lovasz (reserved)
  2. Total coloring conjecture (reserved)
  3. Edge list coloring conjecture
  4. Reed's conjecture
  5. Hedetniemi's conjecture (reserved)
  6. Grunbaum's conjecture
  7. Hadwiger's conjecture (reserved)
  8. Erdos-Faber-Lovasz conjecture (reserved)
  9. Gyafras forbidden induced tree conjecture
  10. 3-coloring arrangements of great circles (reserved)
  11. Coloring the odd distance graph
  12. Counting 3-colorings of the hex lattice
  13. Ringel's earth-moon problem (reserved)
  14. Coloring squares of planar graphs