Perfect graphs with no \(P_ 5\) and no \(K_ 5\)

DOI10.1007/BF02986662zbMath0806.05052OpenAlexW2483513242MaRDI QIDQ1334944

Frédéric Maffray, Myriam Preissmann

Publication date: 26 September 1994

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02986662

zbMATH Keywords

chromatic numberperfect graphcliquestrong perfect graph conjectureforbidden induced subgraphs5-cycle5-clique5-path

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Classes of perfect graphs, On the complexity of 4-coloring graphs without long induced paths, On minimal imperfect graphs without induced \(P_5\), The strong perfect graph conjecture: 40 years of attempts, and its resolution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On conjecture of Berge
• Coloring perfect \((K_ 4\)-e)-free graphs
• A new property of critical imperfect graphs and some consequences
• Locally perfect graphs
• Paw-free graphs
• Graphical properties related to minimal imperfection
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• Perfect zero–one matrices