Overfull graph

In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and its order floored, i.e. $m>\Delta (G)\lfloor n/2\rfloor$ where m is the size of G, $\displaystyle \Delta (G)$ is the maximum degree of G, and n is the order of G. The concept of an overfull subgraph, an overfull graph that is a subgraph, immediately follows. An alternate, stricter definition of an overfull subgraph S of a graph G requires $\displaystyle \Delta (G)=\Delta (S)$ .

Properties

A few properties of overfull graphs:

Overfull graphs are of odd order.
Overfull graphs are Class 2.
A graph G, with an overfull subgraph S such that $\displaystyle \Delta (G)=\Delta (S)$ , is of Class 2.

Overfull conjecture

In 1986, Chetwynd and Hilton posited the following conjecture that is now known as the overfull conjecture.^[1]

A graph G with

\Delta (G)\geq n/3

is Class 2 iff an overfull subgraph S exists such that

\displaystyle \Delta (G)=\Delta (S)

.

This conjecture, if true, would have numerous implications in graph theory, including the 1-factorization conjecture.^[2]

References

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

[1] 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.

[2] 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.

[1]

[2]