Graph families which have polynomial time algorithms for computing the chromatic number

Question

Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings.

---

For which graph families there exists a polynomial time algorithm for computing the chromatic number $\chi(G)$?

The problem is solvable in polynomial time when $\chi(G) = 2$ (bipartite graphs). In general when $\chi(G) \ge 3$, computing the chromatic number is NP-hard, but there are many graph families where this is not the case. For example, colouring cycles and perfect graphs can be done in polynomial time.

Also, for many graph classes, we can simply evaluate the corresponding chromatic polynomial; some examples in Mathworld.

I suppose most of the above is common knowledge. I would gladly learn whether there are any other (non-trivial) graph families for which the minimum graph colouring is solvable in polynomial time.

In particular, I am interested in exact and deterministic algorithms but feel free to point out any interesting randomized algorithms or approximation algorithms.

---

Update (Aug 31):

Thanks to everyone for submitting interesting answers. Here's a short summary of the answers and references.

Perfect and almost perfect graphs

• Geometric Algorithms and Combinatorial Optimization (1988), Chapter 9 (Stable sets in graphs). Martin Grotschel, Laszlo Lovasz , Alexander Schrijver.

Chapter 9 of the book shows how to solve the coloring problem via the minimum weighted clique covering problem. Since they rely on the ellipsoid method, these algorithms may not be very useful in practice. Also, the chapter has a nice reference list for different classes of perfect graphs.

• Combinatorial Optimization (2003), Volume B, Section VI Alexander Schrijver.

This book has three chapters devoted to perfect graphs and their polynomial time colourability. I took only a quick look but the basic approach seems the same as in the previous book.

• A characterization of b-perfect graphs (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Graphs with bounded tree-width or clique-width

• Edge dominating set and colorings on graphs with fixed clique-width (2001). Daniel Kobler, Udi Rotics

The algorithms here require a k-expression (an algebraic formula for constructing a graph with a bounded clique-width) as a parameter. For some graphs, this expression can be computed in linear time.

• Yaroslav pointed out in methods for counting colourings in bounded tree-width graphs. See his answer below.

These two study graph families where $k$ vertices or edges can be either added or deleted.

• Parameterized complexity of vertex colouring (2003). Leizhen Cai.

  Colouring can be solved in polynomial time when adding or deleting $k$ edges (for fixed $k$) in split graphs.

• Parameterized coloring problems on chordal graphs (2006). Dániel Marx.

  For fixed $k$, chordal graphs to which $k$ edges are added, can be coloured in polynomial time.

Graphs not containing particular subgraphs

• Deciding k-Colorability of P5-Free Graphs in Polynomial Time (2010). Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.

• 3-colouring AT-free graphs in polynomial time (2010). Juraj Stacho.

Colouring quadtrees

• Algorithms for coloring quadtrees (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.

Answer 1

As you observe, all perfect graphs can be colored in polynomial time, but I think the proof involves ellipsoid algorithms for linear programming (see the book by Grötschel, Lovász, and Schrijver) rather than anything direct and combinatorial. There are a lot of different classes of graphs that are subclasses of perfect graphs and have easier coloring algorithms; chordal graphs, for instance, can be colored greedily using a perfect elimination ordering.

All locally connected graphs (graphs in which every vertex has a connected neighborhood) can be 3-colored in polynomial time, when a coloring exists: just extend the coloring triangle by triangle.

Graphs of maximum degree three can be colored in polynomial time: it's easy to test whether they're bipartite, and if not then either they require only three colors or they have K4 as a connected component and require four colors (Brooks' theorem).

Triangle-free planar graphs can be colored in polynomial time, for the same reason: they are at most 3-chromatic (Grötzsch's theorem).

Answer 2

b-perfect graphs allow induced 5-cycles (unlike perfect graphs), and were shown to have a polynomial-time algorithm for colouring by Hoàng, Maffray, and Mechebbek, A characterization of b-perfect graphs, arXiv:1004.5306, 2010.

(It is a pity that the wonderful compendium of graph classes at the ISGCI only covers cliquewidth, independent set, and domination. It does not include information about colouring.)

Answer 3

Also for graphs of bounded clique-width (which is more general than treewidth): Kobler and Rotics.

A few more remarks: the running time of the above is pretty bad (because it's a very general graph class), and it has been shown by Fomin et al. (SODA 2009) that chromatic number is W[1]-hard parameterized by cliquewidth (i.e., some $n^{f(k)}$ factor in the running time seems unavoidable).

Also, clique-width is hard to compute, but there is an approximation algorithm by Oum and Seymour, "pproximating clique-width and branch-width" (with exponential approximation).

Putting it together, we get a polynomial running time, where the degree of the polynomial is double-exponential in $k$.

Answer 4

Any family of graphs with bounded tree-width will have a polynomial time algorithm for computing the chromatic number. Gamarnik reduces the problem of counting colorings to that of computing marginals of certain Markov Random Fields defined on the same graph. Result follows because marginals of MRFs on bounded tree-width graphs can be computed in polynomial time with the junction tree algorithm.

Update 8/26: Here's an example of "# of colorings"<->marginals reduction. It requires starting with a proper coloring, which can be found in polynomial time for bounded tree-width graphs with the max-plus version of junction tree algorithm. Now to think of it...you don't really need # of colorings for chromatic number, just a single proper coloring

Answer 5

For every fixed integer k, testing whether a graph without induced $P_5$ subgraphs can be k-colored is solvable in polynomial time ("Deciding k-colorability of P5-free graphs in polynomial time", 2008). Observe that $C_5$ is $P_5$ free and thus the P_5-free graphs are not perfect.

A very recent result which is in the accepted papers list of ISAAC is that 3-colorability of AT-free graphs can also be decided in polynomial time. ( Juraj Stacho, 3-colouring AT-free graphs in polynomial time; paper not yet published but the abstract is at http://tclab.kaist.ac.kr/~otfried/isaac2010-abstracts.html ). The same list also has a result by Hajo Broersma, Petr Golovach, Daniel Paulusma and Jian Song ("On Coloring Graphs Without Induced Forests") that 3-coloring is in P for graphs without induced $2P_3$.

There are also results by Daniel Marx regarding the complexity of the chromatic number problem on graphs which can be made chordal by at most k vertex deletions; for every fixed k this problem is polynomial ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Answer 6

Algorithms for coloring quadtrees.
M. Bern, D. Eppstein, and B. Hutchings.
http://arXiv:cs.CG/9907030.
Algorithmica 32(1):87-94, 2002.

We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.