No odd pairs in minimal imperfect NP₅ graphs.

DOI10.1016/S0020-0190(01)00329-5MaRDI QIDQ1853069zbMATH OpenOpenAlexFDO

Authors Jean-Luc Fouquet

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(01)00329-5

zbMATH Keywords

Graph algorithms

Mathematics Subject Classification ID

Perfect graphs (05C17) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• On minimal imperfect graphs without induced P₅
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• On minimal cutsets in P₅-free minimal imperfect graphs
• No antitwins in minimal imperfect graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On embeddings of graphs containing noK5-minor
• Graphs without induced P₅and C₅
• Towards Erdős-Hajnal for graphs with no 5-hole
• Improper colouring of graphs with no odd clique minor
• A new conjecture about minimal imperfect graphs

Cites work

• A new conjecture about minimal imperfect graphs
• A new property of critical imperfect graphs and some consequences
• Coloring perfect \((K_ 4\)-e)-free graphs
• Discs in unbreakable graphs
• On minimal cutsets in P₅-free minimal imperfect graphs
• On minimal imperfect graphs without induced P₅
• Some properties of minimal imperfect graphs
• Star-cutsets and perfect graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

This page was built for publication: No odd pairs in minimal imperfect NP\({}_{5}\) graphs.

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