OVERVIEW
Graph Coloring Problems
Chapter 1: Introduction to Graph Coloring
- Section 1.1: Basic Definitions
- Section 1.2: Graphs on Surfaces
- January, 1996: Hadwiger's Conjecture for k=4 was first proved by Hadwiger in 1943.
- July, 1997: New reference [B.Toft: A survey of Hadwiger's Conjecture]
- Section 1.3: Vertex Degrees and Colorings
- Section 1.4: Criticality and Complexity
- Section 1.5: Sparse Graphs and Random Graphs
- Section 1.6: Perfect Graphs
- August, 1997: Berge's paper on the history of perfect graphs has appeared.
- July, 2006: The Strong Perfect Graph Conjecture has been solved.
- Section 1.7: Edge-Coloring
- Section 1.8: Orientations and Integer Flows
- Section 1.9: List Coloring
- August, 1997: F. Galvin's proof of the Dinitz conjecture published.
- Section 1.10: Generalized Graph Coloring
- December, 1994: O.V. Borodin gave an independent proof of Theorem 39.
- Section 1.11: Final Remarks
- Bibliography
- August 1997: The following papers have appeared.
- O.V. Borodin 1994a, A new proof of Grünbaum's 3-color theorem.
- M.N. Ellingham and L. Goddyn 1993, List edge
colorings of some regular planar multigraphs.
- C. Thomassen 1993c, Grötzsch's 3-Color Theorem and
its Counterparts for the Torus and the Projective Plane.
Chapter 2: Planar Graphs
- Problem 2.1: Four-Color Theorem
- December, 1994: Manuscript on a new proof of the four color theorem.
- November, 1996: 3-colorability of 4-regular planar graphs is NP-complete.
- August, 1997: The paper [N. Robertson, D.P. Sanders, P. Seymour, and R. Thomas,
The Four-Colour Theorem] has appeared.
- September, 2010: A paper by G. Gonthier gives a formally checkable proof of
The Four-Color Theorem.
- September, 2010: A new proof by J.P. Steinberger uses D-reducibility only.
- Problem 2.13: List-Coloring Planar Graphs
- August, 1995: First part of Problem 2.13 has been solved!
- Bibliography
- August 1997: The following papers have appeared.
- H.L. Abbott, M. Katchalski, and B. Zhou, Proof of a conjecture
of Dirac concerning 4-critical planar graphs.
- O.V. Borodin 1989c, A new proof of the
6 color theorem.
- O.V. Borodin 1990c, Structure, contraction
and cyclic coloring of 3-polytopes.
- O.V. Borodin 1992c, Structural theorem on plane
graphs with application to the entire coloring number.
- O.V. Borodin 1994b, Structural properties of plane graphs without
adjacent triangles and an application to 3-colorings.
- M.N. Ellingham and L. Goddyn 1993, List edge
colorings of some regular planar multigraphs.
- S. Gutner 1994, The complexity of planar graph choosability.
- J. Kratochvíl and Zs. Tuza 1993, Algorithmic complexity of
list colorings.
- D.P. Sanders and Y. Zhao 1994, A note on the three color problem.
- C. Thomassen 1993d, Decomposing planar graphs.
- M. Voigt 1994, A not 3-choosable planar graph without 3-cycles.
Chapter 3: Graphs on Higher Surfaces
- Problem 3.5: Number of 6-Critical Graphs on a Surface
- March, 1995 : Problem 3.5 has been solved!
- August, 1997: New reference [C. Thomassen:
Color-Critical Graphs on a Fixed Surface]
- Problem 3.11: Acyclic Colorings
- December, 1994: Problem 3.11 has been solved!
- August, 1997: New reference [N. Alon, B. Mohar and D.P.
Sanders, On Acyclic Colorings of Graphs on Surfaces]
- Bibliography
- August 1997: The following papers have appeared.
- O.V. Borodin 1989c, A new proof of the 6 color theorem.
- J.P. Hutchinson 1994, Three-coloring graphs embedded on
surfaces with all faces even-sided.
- C. Thomassen 1993c, Grötzsch's 3-Color Theorem and
its Counterparts for the Torus and the Projective Plane.
- D.A. Youngs 1991, 4-chromatic projective graphs.
Chapter 4: Degrees
Chapter 5: Critical Graphs
- Problem 5.9: Number of Critical Subgraphs
- August 1997: Partial results on the Conjecture by Abbott and Zhou [1992]
have been obtained by André E. Kézdy and Hunter S. Snevily.
- Bibliography
- August 1997: The following papers have appeared.
- H.L. Abbott and B. Zhou 1993b, (k-1)-critical
subgraphs of k-critical graphs.
- T.R. Jensen and G.F. Royle 1989, Small
graphs of chromatic number 5 - a computer search.
- X.-Y. Su 1994a, On complete subgraphs of color-critical graphs.
- X.-Y. Su 1994b, Complete (k-1)-subgraphs of k-critical graphs.
Chapter 6: The Conjectures of Hadwiger and Hajós
- Bibliography
- August 1997: The paper [T.R. Jensen and F.B. Shepherd 1993,
Note on a conjecture of Toft] has appeared.
- August 1997: The paper [M. Stiebitz and B. Toft 1993,
An abstract generalization of a map reduction
theorem of Birkhoff] has appeared.
Chapter 7: Sparse Graphs
Chapter 8: Perfect Graphs
- Problem 8.3: Bold Conjecture
- February, 1996: Problem 8.3 has been solved!
- August, 1997: The paper [T. Sakuma, A Counterexample to the
Bold Conjecture] has appeared.
- Bibliography
- August 1997: The paper [C.T. Hoàng, On the two-edge colourings
of perfect graphs] has appeared.
- August 1997: The paper [H.A. Kierstead and V. Rödl 1993,
Applications of hypergraph coloring to coloring of graphs not inducing
certain trees] has appeared.
Chapter 9: Geometric and Combinatorial Graphs
- Bibliography
- June, 1995: Remark on Kahn [1994b].
- August 1997: The paper [H. Sachs 1991, Coin graphs, polyhedra and
conformal mapping] has appeared.
- August 1997: On the reference [A. Soifer, Mathematical Coloring
Book].
Chapter 10: Algorithms
- Problem 10.1: Polynomial Graph Coloring
- August 2000: A very strong negative result concerning the
existence of a polynomial graph coloring algorithm with good
performance guarantee.
- Problem 10.6: On-Line Coloring
- September 1997: Update on lower bounds for the performance function
of an on-line coloring algorithm.
- Bibliography
- September 1997: The paper [M.M. Halldórsson 1990, A still
better performance guarantee for approximate graph coloring] has long
since appeared.
Chapter 11: Constructions
Chapter 12: Edge Colorings
- Problem 12.15: Tutte's Conjecture on 3-Edge
Colorings
- August, 1997: The paper [M. Kochol, Snarks without Small Cycles]
has been published.
- Problem 12.20: List-Edge-Chromatic Numbers
- June, 1995: A remark on the asymptotic behavior of the list-edge-chromatic number of a simple graph
in terms of its maximum degree.
- December, 2000: The series-parallel case of the problem has been solved.
- Bibliography
- August 1997: The paper [K. Kilakos and F.B. Shepherd 1993, Excluding
minors in cubic graphs] has appeared.
- August 1997: The paper [C.-Q. Zhang 1993, Hamilton weights and
unique 3-edge-colorings of cubic graphs] has appeared.
Chapter 13: Orientations and Flows
- Problem 13.2: Tutte's 4-Flow Conjecture
- August, 1997: The paper [M. Kochol, Snarks without Small Cycles]
has been published.
- Bibliography
- August 1997: The following papers have appeared.
- B. Alspach, L. Goddyn and C.-Q. Zhang 1993,
Graphs with the circuit cover property.
- C. Thomassen 1993c, Grötzsch's
3-Color Theorem and its Counterparts for the Torus and the
Projective Plane.
- D.A. Youngs 1993, Minimal orientations of
colour critical graphs.
Chapter 14: Chromatic Polynomials
Chapter 15: Hypergraphs
- Problem 15.1: Erdös' Property B
- August 2010: Bounds for m(4).
- G. Manning obtained the lower bound 21 in his Ph.D. thesis 1997.
- Patric Östergård has made a computer search to obtain the exact value 23.
- Bibliography
- August 1997: The following papers have appeared.
- M. Gionfriddo, S. Milici and Zs. Tuza, Blocking sets in SQS(2v).
- Zs. Tuza, Inequalities for minimal covering sets in set systems
of given rank.
Chapter 16: Infinite Chromatic Graphs
Chapter 17: Miscellaneous Problems
- Problem 17.2: List-Coloring the Union of Graphs
- August, 1997: New references related to Problem 17.2.
- Problem 17.3: Cochromatic Number
- August, 1997: Reference related to cochromatic number.
- August, 1997: Problem 17.3 has been solved!
- Problem 17.14: Winning Hex
- March, 1995: A note on the case m different from n (that is: Hex on a "short" board).
- Bibliography
- August 1997: The paper [D. Hanson, G. MacGillivray and B. Toft 1994,
Vertex list-colouring of bipartite graphs] has appeared.
- August 1997: The paper [P. Mihók 1993,
On the minimal reducible bound for outerplanar and planar graphs]
has appeared.
Last modified August, 2011, Bjarne Toft
and Tommy R. Jensen