A class of perfect graphs containing P₆

DOI10.1016/S0095-8956(02)00022-9MaRDI QIDQ1405124zbMATH OpenFDO

Authors Xinming Liu, Gérard Cornuéjols

Publication date 25 August 2003

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

Full work available at URL https://doi.org/10.1016/S0095-8956(02)00022-9

zbMATH Keywords

DecompositionPerfect graphStar cutset

Mathematics Subject Classification ID

Perfect graphs (05C17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A star cutset is a vertex cutset in which one vertex is adjacent to all the other vertices of the cutset. The authors prove that if a perfect graph \(G\) contains the induced path on six vertices but not two families introduced by M. Conforti and G. Cornuéjols, then \(G\) is bipartite or disconnected, on \(\overline G\) has a star cutset.

Recommendations

• Star-cutsets and perfect graphs
• On minimal cutsets in P₅-free minimal imperfect graphs
• Quasi-star-cutsets and some consequences
• A generalization of Chvátal's star-cutset lemma
• Perfect graphs, partitionable graphs and cutsets

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• On the perfect graph conjecture
• Star-cutsets and perfect graphs
• The strong perfect graph theorem

Cited in

(8)

• Star-cutsets and perfect graphs
• Quasi-star-cutsets and some consequences
• A generalization of Chvátal's star-cutset lemma
• A note on class one graphs with maximum degree six
• scientific article; zbMATH DE number 5844229 (Why is no real title available?)
• Irredundance perfect andP6-free graphs
• A NEW CHARACTERIZATION OF UNBREAKABLE GRAPHS
• On minimal cutsets in P₅-free minimal imperfect graphs

This page was built for publication: A class of perfect graphs containing \(P_{6}\)

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