Graph families which have polynomial time algorithms for computing the chromatic number 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.
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).