Graph coloring

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
Contact: aszek AT math.ku.dk
Office: 04.1.18
Office hours: feel free to stop by my office or send me an e-mail

News

29/03. Posted the third graded homework. Note that 2.(6)=2.666666...=2+2/3=8/3
07/03. A list of open problems to choose from is available at the bottom of the page. Please prepare a max. 10 minute presentation about the problem, mention some examples, partial progress etc. (You are still welcome to choose a problem from outside the list)
04/03. Posted the second graded homework
18/02. Posted the first graded homework
16/02. Due to high popular demand I added a section with precise literature references for our main topic, theorems, proofs, etc.
10/02. You should by all means check out the YouTube channel of Sarada Herke.
10/02. Some inspiration for the short open problem presentation can be found under Literature at the end.
08/02. On top of the homework credit there is extra credit for writing up short lecture notes, so please volunteer.
08/02. Here is a Latex template for writing up lecture notes.
08/02. Please sign up to SageMathCloud to use SAGE online. If you want you can always download and install SAGE on your computer. Documentation is here. Specific reference for graphs is here. If you are familiar with some other computer algebra/combinatorics system then feel free to use it.

Graded assignments

Homework 1: hw1.pdf, graph.sage. Deadline 04/03, 10:16am.
Homework 2: hw2.pdf. Deadline 18/03, 10:16am.
Homework 3: hw3.pdf. Deadline 15/04, 23:59.

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.

Schedule

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.

Literature pointers to some specific topics

[D] Diestel, [BM] Bondy and Murty, [B] Bollobas, [W] West
[AZ] Aigner and Ziegler Proofs from the Book

Various bounds and greedy coloring: [W, 5], [BM, 14], [B, V.1], [D, 5.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]
Mycielski's construction: [W, 5.2], [BM, 14.11]
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.
Cartesian product: [W, 5.1.9-11]
List coloring: [B, V.4], [W, 8.4], [D, 5.4]
Thomassen's 5-list-coloring theorem: [D, 5.4.2], [W, 8.4.32], [B, Thm. V.12], [AZ, Ch. 25]
The art gallery problem: [AZ, Ch. 26], wiki
Chromatic polynomials: [B, V.1], [BM, 14.7], [W, 5.3]
Counting acyclic orientations: [W, 5.3.27], [BM, Ex.14.7.11], [B, Ex.V.50]
Edge chromatic number and line graphs: [B, V.2], [BM, 17], [D, 5.3], [W, 7.1]
Hall's marriage theorem: [B. Thm. III.3.7], [W, 3.1.11], wiki
Vizing's theorem: [B, Thm. V.2.7], [D, 5.3.2], [W, 7.1.10], [BM, 17.2]
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
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].
Compactness theorem for coloring: [S, Thm.26.1]

Planned content

Introduction to graph theory, basic types of graphs, classical graph parameters and relations between them, homomorphisms, the categories of graphs
Vertex coloring, the vertex-chromatic number, its relation to other graph parameters, simple bounds, Brook's theorem, perfect graphs
Graphs with large girth and chromatic number: probabilistically and constructively, Mycielski's graphs
The chromatic polynomial and its properties, chromatic roots, counting acyclic orientations
Coloring graphs on the plane and on surfaces: the 5-color theorem, Thomassen's 5-choosability theorem, Heawood's theorem
Edge coloring and the edge-chromatic number, Vizing's theorem
The Tutte polynomial and its combinatorial specializations. Infomation about matroids and some applications of the Tutte polynomial in various branches of mathematics (statistical physics, knot theory).
The chromatic number of the plane and of Euclidean spaces and spheres. Exponential lower and upper bounds. Algebraic constructions.
Topological preliminaries: The Borsuk-Ulam theorem and the calculation of the chromatic number of Kneser graphs by Lovasz.
Simplicial complexes and some homotopy theory. The neighborhood complex of a graph. Topological lower bounds: Lovasz's theorem. Information about Hom complexes and other topological tools.

Literature

For the first part of the course any standard graduate-level textbook on graph theory will be fine. For instance:

Bondy, Murty, Graph theory esp. ch. 11,13,14,15,17,21
Diestel, Graph theory
West, Introduction to graph theory
Bollobas, Modern graph theory

Information about the topological tools can be found in

Kozlov, Combinatorial algebraic topology, ch. 17

And here is some light reading for long evenings:

Soifer, The Mathematical Coloring Book Mathematics of Coloring and the Colorful Life of its Creators

Open problems related to graph coloring:

Jensen, Toft, Graph Coloring Problems, available in our library in print and as an online resource
Beineke, Wilson, Topics in chromatic graph theory, Chapter 15, available through our library as an online resource
Open Problem Garden

Some open problems in graph coloring to choose from

Double-critical graphs, Lovasz (reserved)
Total coloring conjecture (reserved)
Edge list coloring conjecture
Reed's conjecture
Hedetniemi's conjecture (reserved)
Grunbaum's conjecture
Hadwiger's conjecture (reserved)
Erdos-Faber-Lovasz conjecture (reserved)
Gyafras forbidden induced tree conjecture
3-coloring arrangements of great circles (reserved)
Coloring the odd distance graph
Counting 3-colorings of the hex lattice
Ringel's earth-moon problem (reserved)
Coloring squares of planar graphs