TOPICS
Search

Perfect Graph


A perfect graph is a graph G such that for every induced subgraph of G, the clique number equals the chromatic number, i.e., omega(G)=chi(G). A graph that is not a perfect graph is called an imperfect graph (Godsil and Royle 2001, p. 142).

A graph for which omega(G)=chi(G) (without any requirement that this condition also hold on induced subgraphs) is called a weakly perfect graph. All perfect graphs are therefore weakly perfect by definition.

A graph is strongly perfect if every induced subgraph H has an independent set meeting all maximal cliques of H. While all strongly perfect graphs are perfect, the converse is not necessarily true. Since every P_4-free graph (where P_n is a path graph) is strongly perfect (Ravindra 1999) and every strongly perfect graph is perfect, if a graph is P_4-free, it is perfect.

Perfect graphs were introduced by Berge (1973) motivated in part by determining the Shannon capacity of graphs (Bohman 2003). Note that rather confusingly, perfect graphs are distinct from the class of graphs with perfect matchings.

Every bipartite graph is perfect (Gross and Yellen 2006, p. 385). The perfect graph theorem states that the graph complement of a perfect graph is itself perfect. A graph is therefore perfect iff its complement is perfect. However, determining if a general graph is perfect has been shown to be a polynomial time algorithm (Chudnovsky et al. 2005).

A graph is perfect iff neither the graph G nor its graph complement G^_ has an odd chordless cycle. A graph with no 5-cycle and no larger odd chordless cycle is therefore automatically perfect. This is true since the presence of a chordless 5-cycle in G^_ corresponds to a 5-cycle in G and G^_ can have no chordless 7-cycle or larger since the diagonals of these cycles in G^_ would contain a 5-cycle in G.

A graph can be tested to see if it is perfect using PerfectQ[g] in the Wolfram Language package Combinatorica` .

PerfectGraphs

The numbers of perfect graphs on n=1, 2, ... nodes are 1, 2, 4, 11, 33, 148, 906, 8887, ... (OEIS A052431).

PerfectConnectedGraphs

The numbers of perfect connected graphs on n=1, 2, ... nodes are 1, 1, 2, 6, 20, 105, 724, ... (OEIS A052433).

Classes of graphs that are perfect include:

1. bipartite graphs,

2. block graphs,

3. chordal graphs,

4. distance-hereditary graphs,

5. line graphs of bipartite graphs,

6. Meyniel graphs,

7. trees,

8. graph complements of bipartite graphs, and

9. graph complements of line graphs of bipartite graphs.

Families of perfect graphs (excluding bipartite families) include:

1. barbell graphs,

2. bishop graphs,

3. caveman graphs,

4. complete graphs K_n,

5. n-double cone graphs for n=3 or n even,

6. empty graphs K^__n,

7. fan graphs,

8. Hanoi graphs,

9. helm graphs H_n for n=3 or n even,

10. rook graphs,

11. lollipop graphs,

12. king graphs K_(m,n) with min(m,n)<=3,

13. Ptolemaic graphs,

14. queen graphs Q_(1,n), Q_(2,n) and Q_(3,3),

15. sun graphs,

16. Turán graphs,

17. triangular snake graphs TS_n, and

18. windmill graphs.


See also

Chordal Graph, Chromatic Number, Clique, Imperfect Graph, Induced Subgraph, Odd Chordless Cycle, Perfect Graph Theorem, Perfect Matching, Shannon Capacity, Strong Perfect Graph Theorem, Strongly Perfect Graph, Weakly Perfect Graph

Explore with Wolfram|Alpha

References

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Bohman, T. and Holzman, R. "A Nontrivial Lower Bound on the Shannon Capacities of the Complements of Odd Cycles." IEEE Trans. Inform. Th. 49, 721-722, 2003.Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; and Vušković, K. "Recognizing Berge Graphs." Combinatorica 25, 143-186, 2005.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 142-143, 2001.Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Ravindra, G. "Some Classes of Strongly Perfect Graphs." Disc. Math. 206, 197-203, 1999.Skiena, S. "Perfect Graphs." §5.6.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 219, 1990.Sloane, N. J. A. Sequences A052431 and A052433 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "A Hint of Perfect Graphs" and "Perfect Graphs." §8.1 in Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 226-228 and 319-348, 2000.

Referenced on Wolfram|Alpha

Perfect Graph

Cite this as:

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

Subject classifications