Weakly Perfect Graph

A weakly perfect graph is a graph for which omega(G)=chi(G) (without any requirement that this condition also hold on induced subgraphs, which is required for a graph to be perfect), where omega(G) is the clique number and chi(G) is the chromatic number.

All perfect graphs are weakly perfect.

The numbers of weakly perfect graphs on n=1, 2, ... nodes are 1, 2, 4, 11, 33, 152, 1006, 11805, ... (OEIS A198634).

See also

Chromatic Number, Clique Number, Perfect Graph, Strongly Perfect Graph

Explore with Wolfram|Alpha


Maimani, H. R.; Pournaki, M. ä.; and Yassemi, S. "A Class of Weakly Perfect Graphs." Czech. Math. J. 60, 1037-1041, 2010.Sloane, N. J. A. Sequence A198634 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Weakly Perfect Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications