When Do a Few Colors Suffice?

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

.

Perfect graphs

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.

Mycielski Graphs

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.

Trinity Graphs

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.)

A graph is pentagonal if all its odd holes are pentagons.

Theorem (Chudnovsky, Seymour and Scott 2014): Pentagonal graphs can be colored by 82200 colors.

(The paper: Three steps towards Gyarfas’ conjecture.)

It is possible that all pentagonal graphs are 4-colorable.

Connections with homology: Conjectures by Kalai and Meshulam

Consider the independence complex of a graph, namely the simplicial complex whose faces are independent sets of vertices. For a simplicial complex K let denotes the ith Betti number of K and let b(K) denote the sum of the Betti numbers. Here are a few conjectures made by Roy Meshulam and me about a decade ago.

Conjecture 1: For every C>0 there is K(C)  such that for a graph G if |b(I(H))| ≤ C for every induced subgraph H then G can be colored by K(C) colors.

Conjecture 2:  For a graph G  we have that |b(I(H))| ≤ 1 for every induced subgraph H, if and only if G does not contain an induced cycle of length divisible by 3.

Conjectures 1 and 2 have led us to conjecture the Trinity Theorem now proved by Marthe Bonamy, Pierre Charbit, and Stéphan Thomassé.

Stronger forms of Conjecture 1 are given by:

Conjecture 3:  For every function g, with   there is K(g)  such that for a graph G if |b(I(H))| ≤ g(n(H)) for every induced subgraph H with n(H) vertices, then G can be colored by K(g) colors.

Conjecture 4: For conjectures 1 and 3 we can even replace the sum of Betti numbers by the absolute value of the Euler characteristics.

Graphs whose chromatic number is bounded by some function of their clique number

A variant of Question 2 is:

Question 3: Describe the classes  of graphs closed under induced subgraphs, with the property that for some function f, for every .

We will call such a class of graphs a class of accomplished graphs (with respect to the function f). “Accomplished” is offered as a weak form of “perfect” and being accomplished is an asymptotic property. Of course, I am open to any other name for this property.

Gyarfas conjecture (1985): The class graphs without odd holes of length more than is accomplished.

Theorem (Seymour and Scott 2014):  The class of graphs without odd holes is accomplished.

In other words, for every  t there exists n such that every graph with no subgraph and no odd hole is n-colorable.

Conjecture (Kalai and Meshulam 2005): The class of graphs with b(I(G)) (or even bounded by a fixed polynomial function of the number of vertices is accomplished.

A special case of this conjecture follows from a 2003 theorem by Alon, Kalai, Matousek and Meshulam.

Theorem: The class of graphs with for i>d  is accomplished.

The Erdos-Hajnal Conjecture

One theme for this post is that there is greater hope to understand the chromatic number for a graph and all its induced subgraph than for just an individual graph. Here is a conjecture which puts this insight into a formal mathematical statement.

Conjecture (Erdos and Hajnal) : For every H there is beta such that every graph with  vertices without an induced subgraph isomorphic to H contains a clique of size n or an empty graph of size n.

Erdos classical bound on Ramsey’s numbers asserts that for general graphs you need at least vertices and that vertices suffice.

High Dimensional extensions

My conjectures with Roy and our results actually came from a wider context of higher dimensional complexes. I will not mention this here beside asking

Question 4: What is the “right” extension of perfect graphs for simplicial complexes of dimension greater than one?