Edge Coloring - Open Problems

Open Problems

Jensen & Toft (1995) list 23 open problems concerning edge coloring. They include:

• The conjecture of Gol'dberg (1973) that the chromatic index and fractional index are within one of each other, which would allow the chromatic index to be approximated within one color in polynomial time.
• Several conjectures of Jakobsen and others on the structure of critical graphs for edge coloring, graphs of class 2 such that any subgraph either has smaller maximum degree or is of class 1. Jakobsen originally conjectured that all critical graphs have an odd number of vertices, but this was eventually disproved. Several other conjectures weakening this one, or bounding the numbers of vertices of critical graphs and critical multigraphs, remain open.
• Vizing's problem of classifying the maximum degrees that are possible for class 2 planar graphs.
• The overfull subgraph conjecture of A. J. W. Hilton, stating that graphs with degree at least n/3 are either of class 1 or contain a subgraph with the same degree Δ as the original graph, and with an odd number k of vertices, such that the number of edges in the subgraph is greater than Δ(k − 1)/2, and a similar conjecture by Herbert Grötzsch and Paul Seymour concerning planar graphs in place of high-degree graphs.
• A conjecture of Chetwynd and Hilton (possibly going back earlier to the work of Gabriel Andrew Dirac) that regular graphs with an even number n of vertices and with degree at least n/2 are of class 1.
• A conjecture of Claude Berge and D. R. Fulkerson that the 6-regular multigraphs formed by doubling every edge of a bridgeless 3-regular simple graph may be edge-colored with six colors.
• A conjecture of Fiorini and Wilson that every triangle-free planar graph, other than the claw K_1,3, is not uniquely 3-edge-colorable.