The Overfull Conjecture (1986):

Originator(s): A. G. Chetwynd and A. J. W. Hilton

Conjecture/Question: If a simple graph G with n vertices has maximum degree greater than n/3, then G is Class 1 if and only if G has no overfull subgraph whose maximum degree equals that of G

Definitions/Background/motivation: The minimum number of colors needed to color the edges of G so that incident edges have distinct colors is the edge-chromatic number, \chi'(G). Vizing's Theorem states that \Delta(G) <= \chi'(G) <= \Delta(G)+1 when G is a simple graph. A graph is Class 1 if \chi'(G) = \Delta(G). A subgraph H of a simple graph G is overfull if |V(H)| is odd and 2|E(H)|/(|V(H)|-1) > \Delta(G). In this case G is not \Delta(G)-edge-colorable, so an overfull subgraph is an obstruction to Class 1.

Comments/Partial results: The conjecture was posed in [CH1] and implies the 1-Factorization Conjecture. The best known threshold for maximum degree may still be that overfull subgraphs are necessary for Class 2 when the maximum degree is at least |V(G)|-3. Plantholt [P] proved that overfull subgraphs are necessary for Class 2 if the minimum degree is at least (\sqrt7)|V(G)|/3, using the result of [CH2] on the 1-Factorization Conjecture.

References:
[CH1] Chetwynd, A. G.; Hilton, A. J. W., Star multigraphs with three vertices of maximum degree. Math. Proc. Cambridge Philos. Soc. 100 (1986), no. 2, 303--317.
[CH2] Chetwynd, A. G.; Hilton, A. J. W. $1$-factorizing regular graphs of high degree---an improved bound. Graph theory and combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 103--112.
[P] Plantholt, M., 2003.

Keywords:

Back to Index Page Link to Glossary