Perfect graphs with no P_ 5 and no K_ 5

DOI10.1007/BF02986662MaRDI QIDQ1334944zbMATH OpenOpenAlexFDO

Authors 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 numbercliqueperfect graphforbidden induced subgraphs5-cyclestrong perfect graph conjecture5-clique5-path

Mathematics Subject Classification ID

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

Recommendations

• On the strong perfect graph conjecture
• On a Class of P ₅ -Free Graphs
• On minimal imperfect graphs without induced P₅
• The strong perfect graph conjecture for pan-free graphs
• The strong perfect graph theorem

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3884202 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3902654 (Why is no real title available?)
• scientific article; zbMATH DE number 3902681 (Why is no real title available?)
• A characterization of perfect graphs
• A new property of critical imperfect graphs and some consequences
• Coloring perfect \((K_ 4\)-e)-free graphs
• Graphical properties related to minimal imperfection
• Locally perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• On conjecture of Berge
• Paw-free graphs
• Perfect zero–one matrices
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(15)

• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• On the strong perfect graph conjecture
• On the complexity of 4-coloring graphs without long induced paths
• Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets
• Perfect coloring and linearly χ-boundP6-free graphs
• The strong perfect graph conjecture for pan-free graphs
• A note on the path graph P_k(G)
• The perfect \(T (G)\)-triple system for each subgraph \(G\) of \(K_5\) with eight edges
• Sequential \(NP_5, IP_5, MP_5\) graphs
• On minimal imperfect graphs without induced P₅
• scientific article; zbMATH DE number 2227376 (Why is no real title available?)
• Classes of perfect graphs
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• scientific article; zbMATH DE number 5545494 (Why is no real title available?)
• On a Class of P ₅ -Free Graphs

This page was built for publication: Perfect graphs with no \(P_ 5\) and no \(K_ 5\)

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