Rahul Sharma (Editor)

Overfull graph

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 | > Δ ( G ) ⌊ | V | / 2 ⌋ where | E | is the size of G, Δ ( 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 Δ ( G ) = Δ ( S ) .

Contents

Properties

A few properties of overfull graphs:

  1. Overfull graphs are of odd order.
  2. Overfull graphs are class 2. That is, they require at least Δ + 1 colors in any edge coloring.
  3. A graph G, with an overfull subgraph S such that Δ ( G ) = Δ ( 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 Δ ( G ) ≥ n / 3 is class 2 if and only if it has an overfull subgraph S such that Δ ( G ) = Δ ( S ) .

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

Algorithms

For graphs in which Δ ≥ n 3 , there are at most three induced overfull subgraphs, and it is possible to find an overfull subgraph in polynomial time. When Δ ≥ n 2 , there is at most one induced overfull subgraph, and it is possible to find it in linear time.

References

Overfull graph Wikipedia
(Text) CC BY-SA