When can we properly color the vertices of a graph with a few colors? This is a notoriously difficult problem. Things get a little better if we consider simultaneously a graph together with all its induced subgraphs. Recall that an induced subgraph of a graph G is a subgraph formed by a subset of the vertices of G together with all edges of G spanned on these vertices. An induced cycle of length larger than three is called a hole, and an induced subgraph which is a complement of a cycle of length larger than 3 is called an anti-hole. As usual, is the chromatic number of G and is the clique number of G (the maximum number of vertices that form a complete subgraph. Clearly, for every graph G
Question 1: Describe the class of graphs closed under induced subgraphs, with the property that for every .
A graph G is called perfect if for every induced subgraph H of G. So Question 1 asks for a description of perfect graphs. The study of perfect graphs is among the most important areas of graph theory, and much progress was made along the years.
Interval graphs, chordal graphs, comparability graphs of POSETS , … are perfect.
Two major theorems about perfect graphs, both conjectured by Claude Berge are:
The perfect graph theorem (Lovasz, 1972): The complement of a perfect graph is perfect
The strong perfect graph theorem (Chudnovsky, Robertson, Seymour and Thomas, 2002): A graph is perfect if and only if it does not contain an odd hole and an odd anti-hole.
There are triangle-free graphs with arbitrary large chromatic numbers. An important construction by Mycielski goes as follows: Given a triangle graph G with n vertices create a new graph G’ as follows: add n new vertices and a vertex w. Now add w to each and for every i and j for which and are adjacent add also an edge between and (and thus also between and .)
Classes of Graphs with bounded chromatic numbers
Question 2: Describe classes of graphs closed under induced subgraphs with bounded chromatic numbers.
Here are three theorems in this direction. The first answers affirmatively a conjecture by Kalai and Meshulam. The second and third prove conjectures by Gyarfas.
The Trinity graph theorem (Bonamy, Charbit and Thomasse, 2013): Graphs without induced cycles of length divisible by three have bounded chromatic numbers.
(The paper: Graphs with large chromatic number induce 3k-cycles.)
Steps toward Gyarfas conjecture
Theorem (Scott and Seymour, 2014): Triangle-free graphs without odd induced cycles have bounded chromatic number.
(The paper: Coloring graphs with no odd holes.)