On minimal imperfect graphs without induced P₅

DOI10.1016/S0166-218X(99)00012-8MaRDI QIDQ1293187zbMATH OpenOpenAlexFDO

Authors Vincent Barré, Jean-Luc Fouquet

Publication date 8 May 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00012-8

zbMATH Keywords

chromatic numberperfect graph conjectureminimal imperfect graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Perfect graphs (05C17)

Recommendations

• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• On a Class of P ₅ -Free Graphs
• A survey of the strong perfect graph conjecture and some recent results
• On the strong perfect graph conjecture

Cites work

• scientific article; zbMATH DE number 3884202 (Why is no real title available?)
• scientific article; zbMATH DE number 3891424 (Why is no real title available?)
• scientific article; zbMATH DE number 3902681 (Why is no real title available?)
• scientific article; zbMATH DE number 4065042 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3432293 (Why is no real title available?)
• scientific article; zbMATH DE number 3382402 (Why is no real title available?)
• A characterization of perfect graphs
• A new property of critical imperfect graphs and some consequences
• A note on Hamiltonian circuits
• A note on even pairs
• A note on even pairs
• Bull-free Berge graphs are perfect
• Chair-free Berge graphs are perfect
• Coloring perfect \((K_ 4\)-e)-free graphs
• Graphical properties related to minimal imperfection
• Murky graphs
• New classes of Berge perfect graphs
• On a property of the class of n-colorable graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On the perfect graph conjecture
• On the strong perfect graph conjecture
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• Perfect zero–one matrices
• Short-chorded and perfect graphs
• Some properties of minimal imperfect graphs
• Split-neighbourhood graphs and the strong perfect graph conjecture
• Star-cutsets and perfect graphs
• The connectivity of minimal imperfect graphs
• The strong perfect graph conjecture for pan-free graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Transitiv orientierbare Graphen
• Two classes of perfect graphs

Cited in

(11)

• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• scientific article; zbMATH DE number 3902681 (Why is no real title available?)
• A survey of the strong perfect graph conjecture and some recent results
• Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs
• scientific article; zbMATH DE number 3884202 (Why is no real title available?)
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• On a Class of P ₅ -Free Graphs
• On minimal cutsets in \(P_5\)-free minimal imperfect graphs
• Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable
• The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs

This page was built for publication: On minimal imperfect graphs without induced \(P_5\)

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