Graph Coloring Problems

- 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.

- August 1997: The following papers have appeared.

- 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.

- August 1997: The following papers have appeared.

- 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.

- August 1997: The following papers have appeared.

- Problem 4.3: Color-Bound Families of Graphs
- August 1997: Problem 4.3 has been solved!

- Problem 4.5: Powers of Hamiltonian Cycles
- September 1997: Problem 4.5 has been solved for large values of |V(G)| !

- Problem 4.6: Brooks' Theorem for Triangle-free
Graphs
- September 1998: Reference for the bound of A. Johansson.

- Problem 4.8: k-Chromatic Graphs of Maximum
Degree k
- September 1997: Problem 4.8 has been solved for large values of k !

- Problem 4.9: Total Coloring
- December 1999: Reference for the case of multigraphs of maximum degree at most five.

- Bibliography
- August 1997: The following papers have appeared.
- G. Fan and H.A. Kierstead 1993, The square of paths and cycles.
- A. Sánchez-Arroyo 1993, A new upper bound for total colourings of graphs.
- M. Stiebitz 1993, The forest plus stars colouring problem.

- August 1997: The monograph [H.P. Yap,
*Total Colourings of Graphs*] has appeared.

- August 1997: The following papers have appeared.

- 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.

- August 1997: The following papers have appeared.

- 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.

- Problem 7.3: Smallest Triangle-Free k-Chromatic Graphs
- August, 1995: An asymptotic solution concerning Problem 7.3.
- August, 1997: A remark on greedy coloring of triangle-free graphs.

- Problem 7.6: Number of Odd Cycle Lengths
- August 1997: Problem 7.6 was solved by Gyárfás some years ago!

- Bibliography
- August 1997: The paper [T.R. Jensen and G.F. Royle 1989, Small graphs of chromatic number 5 - a computer search] has appeared.

- 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.

- 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*].

- 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.

- Problem 11.5: Hajós Versus Ore
- January, 1996: Problem 11.5 has been solved!

- Problem 11.6: Length of Hajós Proofs
- January, 1996: Partial results on the complexity of Hajós proofs.

- Problem 11.7: Hajós Constructions of Critical Graphs
- October, 1997: Problem 11.7 has been solved!

- Bibliography
- August 1997: The paper [N. Cizek and S. Klavzar 1993, On the chromatic number of the lexicographic product and the Cartesian sum of graphs] has appeared.
- August 1997: The paper [R. Kaschek and S. Klavzar 1993, Improved bounds for the chromatic number of the lexicographic product of graphs] has appeared.

- 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.

- 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.

- August 1997: The following papers have appeared.

- Problem 14.3: Chromatic Uniqueness
- December, 1994: Historical note concerning Problem 14.3.

- Problem 14.4: Chromatic Equivalence
- December, 1994: Historical note concerning Problem 14.4.

- Problem 14.5: Zeros of Chromatic Polynomials
- December, 1995: The subproblem of determining the maximal zero-free intervals for chromatic polynomials has been solved.

- Bibliography
- August 1997: The paper [C.D. Wakelin 1993, The chromatic polynomial relative to the complete graph basis] has appeared.

- 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.

- August 2010: Bounds for m(4).
- 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.

- August 1997: The following papers have appeared.

- Problem 16.2: Infinite Chromatic Subgraphs
- May, 1995: Erratum concerning the Continuum Hypothesis.

- Problem 16.12: Coloring Number
- August, 1997: Problem 16.12 has been solved!

- 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.