Open Research Index

Almost perfect graph classes

Cicely Henderson, Hidde Koerts, Taite LaGrange, Sophie Spirkl, Agnès Totschnig, Massimo Vicenzo, Rebecca Whitman

arXivarxiv/2609.01906Sep 1, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.01906
curl -X POST /api/v1/records/arxiv/2609.01906/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.01906/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'