Overfull Conjecture

In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and half of its order floored, i.e. $, E, > \Delta (G) \lfloor , V, /2 \rfloor$ where $, E,$ is the size of ''G'', $\displaystyle\Delta(G)$ is the maximum degree of ''G'', and $, V,$ 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. That is, they require at least colors in any edge coloring.
# A graph ''G'', with an overfull subgraph ''S'' such that $\displaystyle\Delta (G) = \Delta (S)$, is of class 2.

Overfull conjecture

In 1986, Amanda Chetwynd and Anthony 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 if and only if it has an overfull subgraph S 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\ge\frac$, there are at most three induced overfull subgraphs, and it is possible to find an overfull subgraph in polynomial time. When $\Delta\ge\frac$, there is at most one induced overfull subgraph, and it is possible to find it in linear time..

References

{{reflist

Graph families