Graph Coloring Problems

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 amazon.com is 125.29 US$ for a new copy and from 100 US$ for a used (amazon.co.uk have corresponding prices of 89.78 £ and 76.82 £).

- Overview
- New problems
- Reviews

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.

Last modified: August, 2011