Title: Combinatorial Designs Related to the Perfect Graph Conjecture
Abstract: This chapter presents combinatorial designs related to the perfect graph conjecture. If G is a graph, then n = n (G) denotes the number of its vertices, α = α (G) denotes the size of its largest stable (independent) set of vertices, and ω = ω (G) denotes the size of its largest clique. The concept of a perfect graph turned out to be one of the most stimulating and fruitful concepts in modern graph theory. A graph is called “minimal imperfect” if it is not perfect itself, but all of its proper induced subgraphs are perfect. Every cycle whose length is odd and at least five is minimal imperfect, and so is its complement. The perfect graph conjecture asserts that there are no other minimal imperfect graphs. The matrix interpretation makes it easier to clarify the role of normalized (α, ω)-graphs.
Publication Year: 1984
Publication Date: 1984-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 25
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot