Almost perfect graph classes

@misc{henderson2026almost,
  title = {{Almost perfect graph classes}},
  author = {Cicely Henderson and Hidde Koerts and Taite LaGrange and Sophie Spirkl and Agnès Totschnig and Massimo Vicenzo and Rebecca Whitman},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.01906},
  eprint = {2609.01906},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.01906},
}

TY  - UNPB
TI  - Almost perfect graph classes
AU  - Cicely Henderson
AU  - Hidde Koerts
AU  - Taite LaGrange
AU  - Sophie Spirkl
AU  - Agnès Totschnig
AU  - Massimo Vicenzo
AU  - Rebecca Whitman
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.01906
UR  - https://arxiv.org/abs/2609.01906
AB  - A graph G is perfect if ω(H) = χ(H) for each induced subgraph H of G. In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem. Motivated by this forbidden induced subgraph characterization of the class of perfect graphs as well as the possible extension of efficient algorithms on perfect graphs, we consider the structure of graphs that are almost perfect. We say a graph is c-apex perfect if there is a constant c number of vertices such that, upon the deletion of these vertices, what remains is a perfect graph. In this paper, we characterize the class of the sets of graphs ℋ with |ℋ|≤ 2 for which there exists c ∈ ℕ with the property that each ℋ-free graph is c-apex perfect. We also extend these results to several notable subclasses of perfect graphs, including chordal, interval, split, bipartite, and complete multipartite graphs.
ER  -