The characterization of strongly perfect graphs by forbidden induced subgraphs
The characterization of strongly perfect graphs by forbidden induced subgraphs
Let be a graph. A graph is strongly perfect if every induced subgraph has a stable set meeting every nonempty maximal clique. An odd hole is an induced cycle of odd length, and an antihole is the complement of an induced cycle; the five graphs labeled I, II, III, IV, and V are the graphs shown in Figure. The strongly perfect graph conjecture. A graph is strongly perfect if and only if it contains no odd holes, no antiholes of length at least six, and none of the graphs I, II, III, IV, or V. The conjecture would provide a forbidden-induced-subgraph characterization of strongly perfect graphs, extending the known characterization for claw-free strongly perfect graphs; the general characterization remains open.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, Cemil Dibek and Paul Seymour, “New Examples of Minimal Non-Strongly-Perfect Graphs”, arXiv:2003.01846 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.