The strong perfect graph conjecture for pan-free graphs

DOI10.1016/0095-8956(89)90019-1MaRDI QIDQ1112848zbMATH OpenOpenAlexFDO

Authors Stephan Olariu

Publication date 1989

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://digitalcommons.odu.edu/cgi/viewcontent.cgi?article=1109&context=computerscience_fac_pubs

zbMATH Keywords

chromatic numberclaw-free graphsclique numberStrong perfect graph conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Review text

A graph \(G\) is perfect if for every induced subgraph \(F\) of \(G\), the chromatic number \(\chi(F)\) equals the largest number \(\omega(F)\) of pairwise adjacent vertices in \(F\). Berge's famous Strong perfect graph conjecture asserts that a graph \(G\) is perfect if and only if neither \(G\) nor its complement \(\overline{G}\) contains an odd chordless cycle of length at least five. Its resolution has eluded researchers for more than twenty years. We prove that the conjecture is true for a class of graphs which strictly contains the claw-free graphs.

Recommendations

• scientific article; zbMATH DE number 1789914
• The strong perfect graph theorem
• On the strong perfect graph conjecture
• Progress on perfect graphs
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)

Cites work

• Critical perfect graphs and perfect 3-chromatic graphs
• scientific article; zbMATH DE number 3315022 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• Star-cutsets and perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(19)

• On minimal imperfect graphs without induced P₅
• Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
• Claw-free graphs---a survey
• Chair-free Berge graphs are perfect
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Decomposition techniques applied to the clique-stable set separation problem
• On the quasi-locally paw-free graphs
• scientific article; zbMATH DE number 3887724 (Why is no real title available?)
• On a Class of P ₅ -Free Graphs
• scientific article; zbMATH DE number 3910416 (Why is no real title available?)
• Set graphs. IV. Further connections with claw-freeness
• scientific article; zbMATH DE number 1339824 (Why is no real title available?)
• scientific article; zbMATH DE number 1789914 (Why is no real title available?)
• On the structure of (pan, even hole)-free graphs
• scientific article; zbMATH DE number 2196277 (Why is no real title available?)
• On the divisibility of graphs
• On independent vertex sets in subclasses of apple-free graphs

This page was built for publication: The strong perfect graph conjecture for pan-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112848)