The perfect graph theorem, proved by László Lovász in 1972, states that an undirected graph is perfect if and only if its complement is also perfect, confirming a conjecture Claude Berge had made in the early 1960s. A perfect graph is one in which the size of the largest clique equals the minimum number of colors needed to color every induced subgraph, a class including bipartite graphs, chordal graphs and comparability graphs; the theorem is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem, which characterizes perfect graphs by forbidden induced subgraphs.
Facts
Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
In Branch
Source Perfect graph theorem (Wikipedia)
Sources
1. Perfect graph theorem (Wikipedia)
Lead section, statement-form reference
In graph theory, the perfect graph theorem of László Lovász (1972a, 1972b) states that an undirected graph is perfect if and only if its complement graph is also perfect.
- In Branch: Graph Theory, Lead sentence
In Group: Graph Theory, Lead section
In graph theory, the perfect graph theorem of László Lovász (1972a
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.