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.
- Algorithms for coloring quadtrees (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.