IMADA /Research activities/
Graph Coloring Problems

Here are the archives for the book "Graph Coloring Problems" by Tommy R. Jensen and Bjarne Toft (Wiley Interscience 1995), dedicated to Paul Erdős.

The book has ISBN number 0-471-02865-7. It is published as part of the Wiley-Interscience Series in Discrete Mathematics and Optimization. The original list price was US$ 44.95. For some years now the book is available only as "print on demand" and the price now (August 2009) on is 125.29 US$ for a new copy and from 100 US$ for a used ( have corresponding prices of 89.78 £ and 76.82 £).

Contributions to be considered for inclusion into the archives may be sent by e-mail to

An interesting graph coloring link is Joseph Culberson's Graph Coloring Page. It contains links to numerous other sites with material of interest for graph coloring.

For general information related to combinatorial mathematics, consult the World Combinatorics Exchange.

Graph Theory with Applications by J.A. Bondy and U.S.R. Murty (Macmillan 1976) was for many years a much used standard graph theory text. It is available on-line - its Appendix IV is a list of 50 unsolved problems (1976).

Introduction to Graph Theory by Douglas West (Prentice Hall 1996 and 2001) is a standard textbook, used in many places, with a well written chapter on graph coloring, but colorings appear also in several other places in the book. It has a final chapter with more advanced material. Douglas west also maintains a webpage with open problems.

Graph Theory by Reinhard Diestel (Springer 1997, 2000, 2005, 2010) gives an introduction to general graph theory including chapters on coloring and integer flows.

Digraphs: Theory, Algorithms and Applications by Jørgen Bang-Jensen and Gregory Gutin (Springer 2001 and 2008) is a comprehensive text on directed graphs, containing material on the relations of graph orientations with coloring and integer flows, and with discussion of directed graph homomorphisms, among other topics.

Graph Theory by J.A. Bondy and U.S.R. Murty (Springer 2008) is a coherent introduction to graph theory for advanced undergraduate and beginning graduate students. It contains several well written chapters on various types of colorings and flows. It contains an appendix with 100 unsolved problems!

The Mathematical Coloring Book by Alexander Soifer (Springer 2009) is an exciting book about the mathematics of coloring and the colorful life of its creators, full of mathematical and historical insight.

A general list of unsolved mathematical problems, called the Open Problem Garden, is maintained at  Simon Fraser University. There are several hundred problems, including 45 graph coloring problems.

Tommy R. Jensen and Bjarne Toft (August 2011)
Last modified: August, 2011