{"id":"arxiv/2609.01906","url":"https://arxiv.org/abs/2609.01906","tags":["math.CO"],"score":0,"title":"Almost perfect graph classes","domain":"math.CO","source":"arxiv","authors":["Cicely Henderson","Hidde Koerts","Taite LaGrange","Sophie Spirkl","Agnès Totschnig","Massimo Vicenzo","Rebecca Whitman"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-01","reactions":{}}