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:

1. Overfull graphs are of odd order.
2. Overfull graphs are Class 2.
3. 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.

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.

Algorithms

For graphs in which $\Delta \geq {\frac {n}{3}}$, there are at most three induced overfull subgraphs, and it is possible to find an overfull subgraph in polynomial time. When $\Delta \geq {\frac {n}{2}}$, there is at most one induced overfull subgraph, and it is possible to find it in linear time.