TOPICS
Search

Imperfect Graph


An imperfect graph G is a graph that is not perfect. Therefore, graphs G with

 omega(G)<chi(G)
(1)

where omega(G) is the clique number and chi(G) is the chromatic number are imperfect. A weaker form using a bound of chi(G) states that a graph with

 n/(alpha(G))<chi(G)
(2)

where alpha(G) is the independence number is imperfect.

By the perfect graph theorem, applying the above to the graph complement gives that a graph G with

 alpha(G)<theta(G)
(3)

where theta(G) is the clique covering number is also imperfect.

A graph is also imperfect iff either the graph or its complement has a chordless cycle of odd order.

Families of imperfect graphs include:

1. cycle graphs C_(2n+1)

2. fullerenes (which by definition contain an odd 5-cycle)

3. king graphs K_(m,n) with min(m,n)>=4

4. helm graphs H_n for odd n>=5

5. wheel graphs W_(2n)

A list of imperfect graphs on small numbers of vertices is implemented in the Wolfram Language as GraphData["Imperfect"].

ImperfectGraphs

The numbers of simple imperfect graphs on n=1, 2, ... vertices are 0, 0, 0, 0, 1, 8, 138, 3459, ... (OEIS A187236).

ImperfectConnectedGraphs

The numbers of connected imperfect graphs on n=1, 2, ... vertices are 0, 0, 0, 0, 1, 7, 129, 3312,... (OEIS A187237).


See also

Perfect Graph

Explore with Wolfram|Alpha

References

Godsil, C. and Royle, G. "Imperfect Graphs." §7.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 142-145, 2001.Sloane, N. J. A. Sequences A187236 and A187237 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "Imperfect Graphs." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 334-340, 2000.

Referenced on Wolfram|Alpha

Imperfect Graph

Cite this as:

Weisstein, Eric W. "Imperfect Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ImperfectGraph.html

Subject classifications