Some aspects of minimal imperfect graphs

MaRDI QIDQ2758338zbMATH OpenFDO

Authors András Sebö, Myriam Preissmann

Publication date 7 August 2002

zbMATH Keywords

chromatic numberclique numberminimal imperfect graphspartitionable graphsperfect graphsstrong perfect graph conjecture

Mathematics Subject Classification ID

Perfect graphs (05C17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

A graph \(G\) is perfect if, for each induced subgraph \(H\) of \(G\), the chromatic number \(\chi(H)\) of \(H\) is equal to the clique number \(\omega(H)\) of \(H\). A graph \(G\) is minimal imperfect if \(G\) is not perfect but every proper induced subgraph of \(G\) is perfect. A graph is partitionable if there exist some integers \(\alpha \geq 2\), \(\omega \geq 2\) such that \(G\) has exactly \(\alpha\omega + 1\) vertices and, for each vertex \(v\), \(G-v\) has both a partition of size \(\alpha\) into cliques and a partition of size \(\omega\) into stable sets. It is well known by the Lovász perfect graph theorem that minimal imperfect graphs are partitionable. Minimal imperfect graphs and partitionable graphs are important concepts in known attempts to prove the famous Berge strong perfect graph conjecture. The paper is a nice and comprehensive survey on these graphs. The authors also discuss several conjectures that may be stronger, weaker, equivalent, independent, or with unknown status compared to the strong perfect graph conjecture.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].

Recommendations

• Some properties of minimal imperfect graphs
• Minimal imperfect graphs: A simple approach
• scientific article; zbMATH DE number 3893228
• A new conjecture about minimal imperfect graphs
• On minimally \(b\)-imperfect graphs
• The connectivity of minimal imperfect graphs
• scientific article; zbMATH DE number 4073014
• On minimally circular-imperfect graphs
• On classes of minimal circular-imperfect graphs
• On vertex neighborhood in minimal imperfect graphs

Cited in

(15)

• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• A new conjecture about minimal imperfect graphs
• \(P_4\)-domination in minimal imperfect graphs
• An approach to solving \(A^{k}=J-I\)
• About skew partitions in minimal imperfect graphs
• Perfect graphs, kernels, and cores of cooperative games
• Grinstead's conjecture is true for graphs with a small clique number
• On strongly stable graphs and some consequences for partitionable graphs
• The theta body and imperfection
• scientific article; zbMATH DE number 1286503 (Why is no real title available?)
• ON A CERTAIN SUBCLASS OF (⍺, ω)-PARTITIONABLE GRAPHS
• Minimal non-neighborhood-perfect graphs
• The connectivity of minimal imperfect graphs
• On vertex neighborhood in minimal imperfect graphs
• On minimally \(b\)-imperfect graphs

This page was built for publication: Some aspects of minimal imperfect graphs

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