When Do a Few Colors Suffice?

Posted on December 19, 2014 by Gil Kalai

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, \chi (G) is the chromatic number of G and \omega (G) is the clique number of G (the maximum number of vertices that form a complete subgraph. Clearly, for every graph G

\chi(G) \ge \omega (G).

Perfect graphs

Question 1: Describe the class \cal G  of graphs closed under induced subgraphs, with the property that \chi(G)=\omega (G) for every G\in{\cal G}.

A graph G is called perfect if  \chi(H)=\omega (H) 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 v_1,v_2, \dots, v_n create a new graph  G’ as follows: add n new vertices u_1, u_2\dots u_n and a vertex w. Now add w to each u_i and for every i and j for which v_i and v_j are adjacent add also an edge between v_i and u_j (and thus also between u_i and v_j.)

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

trinity-youtique-logo

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 b_i(K) 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 g(m)=o(m^2)  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 \cal G  of graphs closed under induced subgraphs, with the property that \chi(G) \le f(\omega (G)) for some function f, for every G \in {\cal G}.

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 \ell 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 K_t subgraph and no odd hole is n-colorable.

Conjecture (Kalai and Meshulam 2005): The class of graphs with b(I(G)) (or even |\chi (I(G))| 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 b_i(I(G))=0 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 n^\beta  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 2^{n/2} vertices and that 2^{2n} 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?

This entry was posted in Combinatorics and tagged . Bookmark the permalink.

5 Responses to When Do a Few Colors Suffice?

  1. gowers says:
    December 21, 2014 at 4:27 pm

    Nice post — I very much like these problems. A small remark is that the link to the paper Three Steps Towards Gyarfas’s Conjecture takes me to a different paper.

    GK: Oops, corrected.

    Reply

  2. Pingback: News on Fractional Helly, Colorful Helly, and Radon | Combinatorics and more

  3. Prajnanaswaroopa S says:
    March 28, 2020 at 4:58 pm

    Recently, a proof of the Total coloring conjecture is posed. You may kindly review the paper and give the feedback. The link is here:https://arxiv.org/pdf/2003.09658

    Reply

  4. Pingback: To cheer you up 14: Hong Liu and Richard Montgomery solved the Erdős and Hajnal’s odd cycle problem | Combinatorics and more

  5. Pingback: To cheer you up in difficult times 25: some mathematical news! (Part 2) | Combinatorics and more

Leave a comment