Graph coloring problems. (English) Zbl 0855.05054

New York, NY: John Wiley & Sons. xix, 295 p. (1995).
In this useful and well-written book, the authors present over 200 open problems in graph coloring. Each problem is chosen for ease of statement and understanding and is accompanied by its historical development and related results, with thorough references. Chapter 1 provides a common basis of terminology and 40 important theorems. The remaining chapters, all self-contained, present the open problems in sixteen categories: (2) Planar Graphs, (3) Graphs on Higher Surfaces, (4) Degrees, (5) Critical Graphs, (6) The Conjecture of Hadwiger and Hajós, (7) Sparse Graphs, (8) Perfect Graphs, (9) Geometric and Combinatorial Graphs, (10) Algorithms, (11) Constructions, (12) Edge Colorings, (13) Orientations and Flows, (14) Chromatic Polynomials, (15) Hypergraphs, (16) Infinite Chromatic Graphs, (17) Miscellaneous Problems (List-Coloring Bipartite Graphs, Harmonious Chromatic Number, Game Chromatic Number, Winning Hex, ten others). Each chapter has its own bibliography. Extensive author and subject indices appear at the end of the book. The book should be very valuable, both as a catalog of open problems (some accessible, some very difficult) and as an extensive survey of known results in the field.


05C15 Coloring of graphs and hypergraphs