<p>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, <em>A characterization of b-perfect graphs</em>, <a href="http://arxiv.org/abs/1004.5306" rel="nofollow">arXiv:1004.5306</a>, 2010.</p>

<p>(It is a pity that the wonderful compendium of graph classes at the <a href="http://wwwteo.informatik.uni-rostock.de/isgci/index.html" rel="nofollow">ISGCI</a> only covers cliquewidth, independent set, and domination.  It does not include information about colouring.)</p>

CC BY-SA 2.5
2010-08-24T14:55:09.737Z
Regarding ISGCI: If independent sets are easy, then it *might* be an indication that colouring could be easy as well. Hence browsing ISGCI might give some fresh ideas for further googling.
Jukka Suomela
CC BY-SA 2.5
2010-08-24T15:16:03.107Z
Moreover, many of the papers cited at the ISGCI do consider colouring as well as CLIQUE/INDEPENDENT SET.  But there are over 1000 references to wade through...
András Salamon
CC BY-SA 2.5
2010-08-24T15:50:07.907Z
Thanks. ISGCI looks promising so perhaps I'll do some browsing there.
Joel Rybicki
CC BY-SA 2.5
2010-08-24T13:38:31.543Z
2010-08-24T13:38:31.543Z
András Salamon
<p>Any family of graphs with bounded <a href="http://en.wikipedia.org/wiki/Tree_decomposition" rel="nofollow">tree-width</a> will have a polynomial time algorithm for computing the chromatic number. Gamarnik <a href="http://arxiv.org/abs/math.CO/0606143" rel="nofollow">reduces</a> 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 <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=825794" rel="nofollow">junction tree</a> algorithm.</p>

<p><b>Update 8/26</b>: Here's an <a href="http://yaroslavvb.com/research/qr/cavity-method/cavityReport.html" rel="nofollow">example</a> of "# of colorings"&lt;->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</p>

CC BY-SA 2.5
2010-08-25T03:11:35.560Z
2010-08-26T23:21:07.210Z
2010-08-26T23:21:07.210Z
Yaroslav Bulatov
<p>Also for graphs of bounded clique-width (which is more general than treewidth): <a href="http://dx.doi.org/10.1016/S0166-218X(02)00198-1">Kobler and Rotics</a>. </p>

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

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

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

CC BY-SA 2.5
2010-08-26T08:33:08.023Z
2010-08-26T08:33:08.023Z
Magnus Wahlström
<p>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.</p>

<p>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 <a href="http://tclab.kaist.ac.kr/~otfried/isaac2010-abstracts.html">http://tclab.kaist.ac.kr/~otfried/isaac2010-abstracts.html</a> ). 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$.</p>

<p>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 ( <a href="http://dx.doi.org/10.1016/j.tcs.2005.10.008">http://dx.doi.org/10.1016/j.tcs.2005.10.008</a> ).</p>

CC BY-SA 2.5
2010-08-24T15:46:53.013Z
Thanks! These references seem quite interesting (particularly, the paper "Deciding k-colorability of P5-free graphs in polynomial).
Joel Rybicki
CC BY-SA 2.5
2010-08-24T14:50:18.337Z
2010-08-24T14:50:18.337Z
Bart Jansen
<p>Algorithms for coloring <strong>quadtrees</strong>. <br/>
M. Bern, D. Eppstein, and B. Hutchings. <br/>
<a href="http://arXiv:cs.CG/9907030" rel="nofollow">http://arXiv:cs.CG/9907030</a>.<br/>
Algorithmica 32(1):87-94, 2002.</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 2.5
2010-08-24T13:29:34.743Z
2010-08-24T13:29:34.743Z
Aryabhata
<p>As you observe, all <a href="http://en.wikipedia.org/wiki/Perfect_graph">perfect graphs</a> 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.</p>

<p>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.</p>

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

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

CC BY-SA 2.5
2010-08-24T17:30:18.483Z
2010-08-24T17:30:18.483Z
David Eppstein
<p><strong>Post updated on 31st of August</strong>: 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.</p>
<hr />
<p>For which graph families there exists a polynomial time algorithm for computing the chromatic number <span class="math-container">$\chi(G)$</span>?</p>
<p>The problem is solvable in polynomial time when <span class="math-container">$\chi(G) = 2$</span> (bipartite graphs).
In general when <span class="math-container">$\chi(G) \ge 3$</span>, 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.</p>
<p>Also, for many graph classes, we can simply evaluate the corresponding chromatic polynomial; some examples in <a href="https://mathworld.wolfram.com/ChromaticPolynomial.html" rel="nofollow noreferrer">Mathworld</a>.</p>
<p>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.</p>
<p>In particular, I am interested in exact and deterministic algorithms but feel free to point out any interesting randomized algorithms or approximation algorithms.</p>
<hr />
<p><strong>Update (Aug 31):</strong></p>
<p>Thanks to everyone for submitting interesting answers. Here's a short summary of the answers and references.</p>
<p>Perfect and almost perfect graphs</p>
<ul>
<li><em>Geometric Algorithms and Combinatorial Optimization</em> (1988), Chapter 9 (Stable sets in graphs).  Martin Grotschel, Laszlo Lovasz , Alexander Schrijver.</li>
</ul>
<p>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.</p>
<ul>
<li><em>Combinatorial Optimization</em> (2003), Volume B, Section VI
Alexander Schrijver.</li>
</ul>
<p>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.</p>
<ul>
<li><a href="https://arxiv.org/abs/1004.5306v1" rel="nofollow noreferrer">A characterization of b-perfect graphs</a> (2010).
Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek</li>
</ul>
<p>Graphs with bounded tree-width or clique-width</p>
<ul>
<li><a href="https://dx.doi.org/10.1016/S0166-218X(02)00198-1" rel="nofollow noreferrer">Edge dominating set and colorings on graphs with fixed clique-width</a> (2001).
Daniel Kobler, Udi Rotics</li>
</ul>
<p>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.</p>
<ul>
<li>Yaroslav pointed out in methods for counting colourings in bounded tree-width graphs. See his answer below.</li>
</ul>
<p>These two study graph families where <span class="math-container">$k$</span> vertices or edges can be either added or deleted.</p>
<ul>
<li><p><a href="https://dx.doi.org/10.1016/S0166-218X(02)00198-1" rel="nofollow noreferrer">Parameterized complexity of vertex colouring</a> (2003).
Leizhen Cai.</p>
<p>Colouring can be solved in polynomial time when adding or deleting <span class="math-container">$k$</span> edges (for fixed <span class="math-container">$k$</span>) in <a href="https://en.wikipedia.org/wiki/Split_graph" rel="nofollow noreferrer">split graphs</a>.</p>
</li>
<li><p><a href="https://dx.doi.org/10.1016/j.tcs.2005.10.008" rel="nofollow noreferrer">Parameterized coloring problems on chordal graphs</a> (2006).
Dániel Marx.</p>
<p>For fixed <span class="math-container">$k$</span>, chordal graphs to which <span class="math-container">$k$</span> edges are added, can be coloured in polynomial time.</p>
</li>
</ul>
<p>Graphs not containing particular subgraphs</p>
<ul>
<li><p><a href="https://link.springer.com/article/10.1007/s00453-008-9197-8?from=SL" rel="nofollow noreferrer">Deciding k-Colorability of P5-Free Graphs in Polynomial Time</a> (2010).
Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.</p>
</li>
<li><p><a href="http://www.cs.toronto.edu/%7Estacho/public/3col-atfree3.pdf" rel="nofollow noreferrer">3-colouring AT-free graphs in polynomial time</a> (2010).
Juraj Stacho.</p>
</li>
</ul>
<p>Colouring quadtrees</p>
<ul>
<li><a href="https://arxiv.org/abs/cs/9907030" rel="nofollow noreferrer">Algorithms for coloring quadtrees</a> (1999).
David Eppstein, Marshall W. Bern, Brad Hutchings.</li>
</ul>

CC BY-SA 3.0
2013-05-19T03:15:25.617Z
Your link for Cai's paper is incorrect.
Jeremy Kun
CC BY-SA 2.5
2010-08-26T10:37:37.363Z
Comparison graphs. This is likely one of the trivial families but I still think they should be mentioned, which is why I use a comment instead of an answer.
Radu GRIGore
CC BY-SA 2.5
2010-08-31T08:59:05.617Z
Did you mean comparability graphs or are comparison graphs a different class?
Joel Rybicki
CC BY-SA 2.5
2010-08-31T10:57:24.863Z
I meant comparability graphs, which are perfect.
Radu GRIGore
CC BY-SA 2.5
2010-08-31T14:57:53.407Z
Note that b-perfect graphs are "close" to being perfect, but are not quite so, as they may contain 5-cycles.
András Salamon
<ds.algorithms><graph-theory><co.combinatorics>
Graph families which have polynomial time algorithms for computing the chromatic number
Joel Rybicki
# Graph families which have polynomial time algorithms for computing the chromatic number

(Asked by: username_0 on 2010-08-24)

**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](https://mathworld.wolfram.com/ChromaticPolynomial.html).

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](https://arxiv.org/abs/1004.5306v1) (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](https://dx.doi.org/10.1016/S0166-218X(02)00198-1) (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](https://dx.doi.org/10.1016/S0166-218X(02)00198-1) (2003).
  Leizhen Cai.

  Colouring can be solved in polynomial time when adding or deleting $k$ edges (for fixed $k$) in [split graphs](https://en.wikipedia.org/wiki/Split_graph).
* [Parameterized coloring problems on chordal graphs](https://dx.doi.org/10.1016/j.tcs.2005.10.008) (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](https://link.springer.com/article/10.1007/s00453-008-9197-8?from=SL) (2010).
  Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.
* [3-colouring AT-free graphs in polynomial time](http://www.cs.toronto.edu/%7Estacho/public/3col-atfree3.pdf) (2010).
  Juraj Stacho.

Colouring quadtrees

* [Algorithms for coloring quadtrees](https://arxiv.org/abs/cs/9907030) (1999).
  username_9, Marshall W. Bern, Brad Hutchings.

**Tags:** ds.algorithms, graph-theory, co.combinatorics

> **Comments:**
> **username_2**: Comparison graphs. This is likely one of the trivial families but I still think they should be mentioned, which is why I use a comment instead of an answer.  
> **username_0**: Did you mean comparability graphs or are comparison graphs a different class?  
> **username_2**: I meant comparability graphs, which are perfect.  
> **username_3**: Note that b-perfect graphs are "close" to being perfect, but are not quite so, as they may contain 5-cycles.  
> **username_1**: Your link for Cai's paper is incorrect.  

---

## 6 answers

### Answer by username_9 on 2010-08-24. Score: 15 | Accepted answer

As you observe, all [perfect graphs](http://en.wikipedia.org/wiki/Perfect_graph) 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 by username_3 on 2010-08-24. Score: 8

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](http://arxiv.org/abs/1004.5306), 2010.

(It is a pity that the wonderful compendium of graph classes at the [ISGCI](http://wwwteo.informatik.uni-rostock.de/isgci/index.html) only covers cliquewidth, independent set, and domination. It does not include information about colouring.)

> **Comments:**
> **username_4**: Regarding ISGCI: If independent sets are easy, then it *might* be an indication that colouring could be easy as well. Hence browsing ISGCI might give some fresh ideas for further googling.  
> **username_3**: Moreover, many of the papers cited at the ISGCI do consider colouring as well as CLIQUE/INDEPENDENT SET.  But there are over 1000 references to wade through...  
> **username_0**: Thanks. ISGCI looks promising so perhaps I'll do some browsing there.  

---

### Answer by username_5 on 2010-08-25. Score: 8

Any family of graphs with bounded [tree-width](http://en.wikipedia.org/wiki/Tree_decomposition) will have a polynomial time algorithm for computing the chromatic number. Gamarnik [reduces](http://arxiv.org/abs/math.CO/0606143) 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](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=825794) algorithm.

**Update 8/26**: Here's an [example](http://yaroslavvb.com/research/qr/cavity-method/cavityReport.html) 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 by username_6 on 2010-08-26. Score: 8

Also for graphs of bounded clique-width (which is more general than treewidth): [Kobler and Rotics](http://dx.doi.org/10.1016/S0166-218X(02)00198-1).

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 by username_7 on 2010-08-24. Score: 7

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

> **Comments:**
> **username_0**: Thanks! These references seem quite interesting (particularly, the paper "Deciding k-colorability of P5-free graphs in polynomial).  

---

### Answer by username_8 on 2010-08-24. Score: 4

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.


---

