Enhanced descriptions from Syndetics:

Contains a wealth of information previously scattered in research journals, conference proceedings and technical reports. Identifies more than 200 unsolved problems. Every problem is stated in a self-contained, extremely accessible format, followed by comments on its history, related results and literature. The book will stimulate research and help avoid efforts on solving already settled problems. Each chapter concludes with a comprehensive list of references which will lead readers to original sources, important contributions and other surveys.

Table of contents provided by Syndetics

• Preface (p. xv)
• 1 Introduction to Graph Coloring (p. 1)
• 1.1 Basic Definitions (p. 1)
• 1.2 Graphs on Surfaces (p. 3)
• 1.3 Vertex Degrees and Colorings (p. 7)
• 1.4 Criticality and Complexity (p. 8)
• 1.5 Sparse Graphs and Random Graphs (p. 12)
• 1.6 Perfect Graphs (p. 13)
• 1.7 Edge-Coloring (p. 15)
• 1.8 Orientations and Integer Flows (p. 17)
• 1.9 List Coloring (p. 18)
• 1.10 Generalized Graph Coloring (p. 21)
• 1.11 Final Remarks (p. 23)
• Bibliography (p. 23)
• 2 Planar Graphs (p. 31)
• 2.1 Four-Color Theorem (p. 31)
• 2.2 Cartesian Sequences (p. 35)
• 2.3 Intersection Graphs of Planar Segments (p. 36)
• 2.4 Ringel's Earth-Moon Problem (p. 36)
• 2.5 Ore and Plummer's Cyclic Chromatic Number (p. 37)
• 2.6 Vertex Partitionings w.r.t. Coloring Number (p. 38)
• 2.7 Vertex Partitionings w.r.t. Maximum Degree (p. 40)
• 2.8 The Three-Color Problem (p. 41)
• 2.9 Steinberg's Three-Color Problem (p. 42)
• 2.10 Grunbaum and Havel's Three-Color Problem (p. 44)
• 2.11 Grotzsch and Sachs' Three-Color Problem (p. 44)
• 2.12 Barnette's Conjecture (p. 45)
• 2.13 List-Coloring Planar Graphs (p. 46)
• 2.14 Kronk and Mitchem's Entire Chromatic Number (p. 47)
• 2.15 Nine-Color Conjecture (p. 48)
• 2.16 Uniquely Colorable Graphs (p. 48)
• 2.17 Density of 4-Critical Planar Graphs (p. 49)
• 2.18 Square of Planar Graphs (p. 50)
• Bibliography (p. 51)
• 3 Graphs on Higher Surfaces (p. 59)
• 3.1 Heawood's Empire Problem (p. 59)
• 3.2 Grunbaum's 3-Edge-Color Conjecture (p. 61)
• 3.3 Albertson's Four-Color Problem (p. 62)
• 3.4 Improper Colorings (p. 63)
• 3.5 Number of 6-Critical Graphs on a Surface (p. 64)
• 3.6 Toroidal Polyhedra (p. 65)
• 3.7 Polynomial Coloring of Embedded Graphs (p. 66)
• 3.8 Sparse Embedded Graphs (p. 66)
• 3.9 Ringel's 1-Chromatic Number (p. 67)
• 3.10 Borodin's Conjecture on Diagonal Coloring (p. 69)
• 3.11 Acyclic Colorings (p. 69)
• 3.12 Cochromatic Numbers (p. 70)
• 3.13 Graphs on Pseudo-Surfaces (p. 70)
• Bibliography (p. 73)
• 4 Degrees (p. 77)
• 4.1 The Coloring Number (p. 77)
• 4.2 Coloring of Decomposable Graphs (p. 79)
• 4.3 Color-Bound Families of Graphs (p. 80)
• 4.4 Edge-Disjoint Placements (p. 81)
• 4.5 Powers of Hamilton Cycles (p. 82)
• 4.6 Brooks' Theorem for Triangle-Free Graphs (p. 83)
• 4.7 Graphs Without Large Complete Subgraphs (p. 85)
• 4.8 k-Chromatic Graphs of Maximum Degree k (p. 85)
• 4.9 Total Coloring (p. 86)
• 4.10 Equitable Coloring (p. 89)
• 4.11 Acyclic Coloring (p. 89)
• 4.12 Melnikov's Valency-Variety Problem (p. 90)
• 4.13 Induced-Odd Degree Subgraphs (p. 90)
• 4.14 Strong Chromatic Number (p. 91)
• Bibliography (p. 92)
• 5 Critical Graphs (p. 97)
• 5.1 Critical Graphs With Many Edges (p. 97)
• 5.2 Minimum Degree of 4- and 5-Critical Graphs (p. 98)
• 5.3 Critical Graphs With Few Edges (p. 99)
• 5.4 Four-Critical Amenable Graphs (p. 101)
• 5.5 Four-Critical Degree 5 Problem (p. 101)
• 5.6 Large Critical Subgraphs of Critical Graphs (p. 102)
• 5.7 Critical Subgraph Covering a 2-Path (p. 102)
• 5.8 Noninduced Critical Subgraphs (p. 103)
• 5.9 Number of Critical Subgraphs (p. 103)
• 5.10 Subgraphs of Critical Graphs (p. 104)
• 5.11 Minimal Circumference of Critical Graphs (p. 104)
• 5.12 The Erdos-Lovasz Tihany Problem (p. 104)
• 5.13 Partial Joins of Critical Graphs (p. 105)
• 5.14 Vertex-Critical Graphs Without Critical Edges (p. 105)
• Bibliography (p. 106)
• 6 The Conjectures of Hadwiger and Hajos (p. 109)
• 6.1 Hadwiger's Conjecture (p. 109)
• 6.2 Hajos' Conjecture (p. 111)
• 6.3 The (m, n)- and [m, n]-Conjectures (p. 112)
• 6.4 Hadwiger Degree of a Graph (p. 114)
• 6.5 Graphs Without Odd-K[subscript 5] (p. 115)
• 6.6 Scheme Conjecture (p. 115)
• 6.7 Chromatic 4-Schemes (p. 116)
• 6.8 Odd Subdivisions of K[subscript 4] (p. 116)
• 6.9 Nonseparating Odd Cycles in 4-Critical Graphs (p. 117)
• 6.10 Minimal Edge Cuts in Contraction-Critical Graphs (p. 117)
• 6.11 Kostochka's Conjecture on Hadwiger Number (p. 117)
• Bibliography (p. 119)
• 7 Sparse Graphs (p. 122)
• 7.1 Blanche Descartes' Triangle-Free Graphs (p. 122)
• 7.2 Grunbaum's Girth Problem (p. 123)
• 7.3 Smallest Triangle-Free k-Chromatic Graphs (p. 123)
• 7.4 Large Bipartite Subgraphs of Triangle-Free Graphs (p. 126)
• 7.5 Sparse Subgraphs (p. 126)
• 7.6 Number of Odd Cycle Lengths (p. 127)
• 7.7 Maximum Girth of k-Chromatic Graphs (p. 127)
• 7.8 Maximum Ratio X/[omega] (p. 128)
• 7.9 Chromatic Number of Sparse Random Graphs (p. 128)
• Bibliography (p. 129)
• 8 Perfect Graphs (p. 131)
• 8.1 Strong Perfect Graph Conjecture (p. 131)
• 8.2 Markosyan's Perfect Graph Problems (p. 132)
• 8.3 Bold Conjecture (p. 133)
• 8.4 Raspail (Short-Chorded) Graphs (p. 134)
• 8.5 "Semistrong" Perfect Graph Conjecture (p. 134)
• 8.6 Hoang's Conjecture on 2-Coloring Edges (p. 135)
• 8.7 Neighborhood Perfect Graphs (p. 135)
• 8.8 Monsters (p. 136)
• 8.9 Square-Free Berge Graphs (p. 137)
• 8.10 Weakened Strong Perfect Graph Conjecture (p. 138)
• 8.11 Gyarfas' Forbidden Subgraph Conjecture (p. 139)
• 8.12 Quasiperfect Graphs (p. 140)
• 8.13 Perfect Graph Recognition (p. 141)
• 8.14 t-Perfect Graphs (p. 144)
• Bibliography (p. 145)
• 9 Geometric and Combinatorial Graphs (p. 150)
• 9.1 Hadwiger--Nelson Problem (p. 150)
• 9.2 Ringel's Circle Problem (p. 152)
• 9.3 Sachs' Unit-Sphere Problem (p. 153)
• 9.4 Sphere Colorings (p. 153)
• 9.5 Graphs of Large Distances (p. 154)
• 9.6 Prime Distance Graphs (p. 155)
• 9.7 Cube-Like Graphs (p. 156)
• 9.8 Odd Graph Conjecture (p. 158)
• 9.9 Chord Intersection Graphs (p. 158)
• 9.10 Gyarfas and Lehel's Triangle-Free L-Graphs (p. 159)
• 9.11 Erdos--Faber--Lovasz Problem (p. 160)
• 9.12 Alon--Saks--Seymour Problem (p. 161)
• 9.13 General Kneser Graphs (p. 161)
• 9.14 Question of Gallai Related to Sperner's Lemma (p. 162)
• Bibliography (p. 163)
• 10 Algorithms (p. 168)
• 10.1 Polynomial Graph Coloring (p. 168)
• 10.2 Polynomial Approximation (p. 169)
• 10.3 Even Chromatic Graphs (p. 169)
• 10.4 Grundy Number (p. 170)
• 10.5 Achromatic Number of a Tree (p. 171)
• 10.6 On-Line Coloring (p. 172)
• 10.7 Edge-Coloring Multigraphs (p. 174)
• 10.8 Complexity of Directed-Graph Coloring (p. 175)
• 10.9 Precedence Constrained 3-Processor Scheduling (p. 176)
• Bibliography (p. 177)
• 11 Constructions (p. 180)
• 11.1 Direct Product (p. 180)
• 11.2 Wreath Product (p. 181)
• 11.3 A Very Strong Product (p. 182)
• 11.4 Gallai's Problem on Dirac's Construction (p. 183)
• 11.5 Hajos Versus Ore (p. 183)
• 11.6 Length of Hajos Proofs (p. 184)
• 11.7 Hajos Constructions of Critical Graphs (p. 185)
• 11.8 Construction of Hajos Generalized by Dirac (p. 185)
• 11.9 Four-Chromaticity in Terms of 3-Colorability (p. 186)
• Bibliography (p. 187)
• 12 Edge Colorings (p. 190)
• 12.1 Goldberg's Conjecture (p. 190)
• 12.2 Jakobsen's Conjecture (p. 191)
• 12.3 Seymour's r-Multigraph Conjecture (p. 192)
• 12.4 Weak Critical Graph Conjecture (p. 192)
• 12.5 Critical Multigraph Conjecture (p. 193)
• 12.6 Vizing's 2-Factor Conjecture (p. 193)
• 12.7 Vizing's Planar Graph Conjecture (p. 193)
• 12.8 Minimal Number of Edges in X'-Critical Graphs (p. 194)
• 12.9 Independent Sets in X'-Critical Graphs (p. 194)
• 12.10 Hilton's Overfull Subgraph Conjecture (p. 195)
• 12.11 The [Delta]-Subgraph Conjecture (p. 195)
• 12.12 Regular Graphs of High Degree (p. 196)
• 12.13 Berge and Fulkerson's Conjecture (p. 197)
• 12.14 Petersen Coloring (p. 197)
• 12.15 Tutte's Conjecture on 3-Edge Colorings (p. 198)
• 12.16 Grotzsch and Seymour's Conjecture (p. 199)
• 12.17 Cycle-Decomposable 4-Regular Plane Multigraphs (p. 200)
• 12.18 Seymour's Planar 4-Multigraph Conjecture (p. 200)
• 12.19 Uniquely 3-Edge-Colorable Planar Graphs (p. 200)
• 12.20 List-Edge-Chromatic Numbers (p. 201)
• 12.21 Strong Chromatic Index (p. 202)
• 12.22 Vizing's Interchange Problem (p. 203)
• 12.23 Scheduling Without Waiting Periods (p. 203)
• Bibliography (p. 205)
• 13 Orientations and Flows (p. 209)
• 13.1 Tutte's 5-Flow Conjecture (p. 209)
• 13.2 Tutte's 4-Flow Conjecture (p. 210)
• 13.3 Tutte's 3-Flow Conjecture (p. 212)
• 13.4 Bouchet's 6-Flow Conjecture (p. 213)
• 13.5 Jaeger's Circular Flow Conjecture (p. 213)
• 13.6 Berge's Strong Path Partition Conjecture (p. 214)
• 13.7 Berge's Directed Path-Conjecture (p. 214)
• 13.8 Minimal Orientations of Critical Graphs (p. 215)
• 13.9 Alon--Tarsi Orientations and Chromatic Number (p. 216)
• Bibliography (p. 218)
• 14 Chromatic Polynomials (p. 220)
• 14.1 Coefficients of Chromatic Polynomials (p. 220)
• 14.2 Characterization of Chromatic Polynomials (p. 221)
• 14.3 Chromatic Uniqueness (p. 221)
• 14.4 Chromatic Equivalence (p. 223)
• 14.5 Zeros of Chromatic Polynomials (p. 225)
• 14.6 Beraha Conjecture (p. 226)
• 14.7 Chessboard Problem (p. 226)
• 14.8 Coefficients for Hypergraphs (p. 227)
• Bibliography (p. 227)
• 15 Hypergraphs (p. 231)
• 15.1 Erdos' Property B (p. 231)
• 15.2 Property B(s) (p. 232)
• 15.3 Finite Projective Planes (p. 233)
• 15.4 Steiner Triple Systems (p. 234)
• 15.5 Steiner Quadruple Systems (p. 235)
• 15.6 Minimum-Weight 3-Chromatic Hypergraphs (p. 235)
• 15.7 Positional Games (p. 236)
• 15.8 Tic-Tac-Toe (p. 237)
• 15.9 Square Hypergraphs (p. 239)
• 15.10 Size of 3-Chromatic Uniform Cliques (p. 241)
• 15.11 Monochromatic Sum-Sets (p. 241)
• 15.12 Arithmetic Progressions (p. 242)
• 15.13 Unprovability (p. 243)
• 15.14 The Direct Product of Hypergraphs (p. 244)
• 15.15 Maximal Complete Subgraphs in Perfect Graphs (p. 244)
• 15.16 Coloring Triangulable Manifolds (p. 245)
• 15.17 Berge's Conjecture on Edge-Coloring (p. 246)
• Bibliography (p. 247)
• 16 Infinite Chromatic Graphs (p. 251)
• 16.1 Sparse Subgraphs of High Chromatic Number (p. 251)
• 16.2 Infinite Chromatic Subgraphs (p. 252)
• 16.3 Almost Bipartite Subgraphs (p. 252)
• 16.4 Large Finite n-Chromatic Subgraphs (p. 253)
• 16.5 Trees in Triangle-Free Graphs (p. 253)
• 16.6 Unavoidable Classes of Finite Subgraphs (p. 254)
• 16.7 4-Chromatic Subgraphs (p. 254)
• 16.8 Avoiding 5-Cycles and Large Bipartite Subgraphs (p. 255)
• 16.9 Connectivity of Subgraphs (p. 255)
• 16.10 Set of Odd Cycle Lengths (p. 255)
• 16.11 Unavoidable Cycle Lengths (p. 256)
• 16.12 Coloring Number (p. 257)
• 16.13 Direct Product (p. 257)
• 16.14 Partition Problem of Galvin and Hajnal (p. 258)
• 16.15 Small Subgraphs of Large Chromatic Number (p. 258)
• Bibliography (p. 259)
• 17 Miscellaneous Problems (p. 261)
• 17.1 List-Coloring Bipartite Graphs (p. 261)
• 17.2 List-Coloring the Union of Graphs (p. 262)
• 17.3 Cochromatic Number (p. 262)
• 17.4 Star Chromatic Number (p. 263)
• 17.5 Harmonious Chromatic Number (p. 264)
• 17.6 Achromatic Number (p. 264)
• 17.7 Subchromatic Number (p. 265)
• 17.8 Multiplicative Graphs (p. 265)
• 17.9 Reducible Graph Properties (p. 266)
• 17.10 T-Colorings (p. 267)
• 17.11 Game Chromatic Number (p. 268)
• 17.12 Harary and Tuza's Coloring Games (p. 269)
• 17.13 Coloring Extension Game (p. 270)
• 17.14 Winning Hex (p. 271)
• Bibliography (p. 272)
• Author Index (p. 277)
• Subject Index (p. 287)

Reviews provided by Syndetics

CHOICE Review

For a century, until its solution in 1976, the Four Color Conjecture was one of the notorious unsolved problems in mathematics. Upon its solution by K. Appel and W. Haken, the four-color theorem was instantly mathematics' most notorious solved problem, for the proof depended on thousands of hours of machine computation that could not be checked by hand on top of 500 pages of dense argumentation. This book describes more than 200 related problems still unsolved, for as the authors remind us, quoting W.T. Tutte, "The Four Colour Theorem is the tip of the iceberg, the thin end of the wedge and the first cuckoo of spring." Problem books like this guide experts and excite the imaginations of serious undergraduates. Similar efforts in other domains may suffer by dint of falling immediately out of date, but these authors are ready to distribute updates via the Internet. And the book itself is timely indeed, for it even surveys the as-yet unpublished, simplified, 1994 four-color theorem proof of N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas. Highly recommended. Undergraduate through faculty. D. V. Feldman; University of New Hampshire

Author notes provided by Syndetics

Tommy R. Jensen, Msc, and Bjarne Toft, PhD, are graph theorists in the Department of Mathematics and Computer Science, Odense University, Denmark