**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:**