Polynomial-time Coloring on even-hole-free graphs
Open Problem: Polynomial-time Coloring on even-hole-free graphs · arXiv:2407.08927
Status open high confidence
The question of whether a polynomial-time algorithm for computing the chromatic number exists on even-hole-free graphs remains open as of May 2026. The source paper (arXiv:2407.08927) established only quasi-polynomial-time results via tree independence number, explicitly leaving the polynomial-time coloring question unresolved. No subsequent paper was found that resolves this problem; related polynomial-time results exist only for strict subclasses such as (cap, even-hole)-free graphs and even-hole-free graphs with no star cutset.
Reviewer notes. No follow-up paper resolving the conjecture was found across three web searches and two WebFetch calls to the arxiv abstract page and Semantic Scholar. Polynomial-time coloring is known for restricted subclasses (e.g., (cap, even-hole)-free graphs, even-hole-free graphs with no star cutset) but the full even-hole-free class remains open. The paper's quasi-polynomial-time QPTAS via tree independence number (tree-independence number O(log^10 n)) does not resolve chromatic number computation.
Context
On even-hole-free graphs, the question of whether a polynomial-time algorithm for Coloring exists remains open, in stark contrast to perfect graphs where polynomial-time algorithms have been known since 1981. The paper's quasi-polynomial-time results via tree independence number do not resolve this question.
Notes. Stated in prose in the introduction without a labelled theorem environment; paired with the MWIS open problem as long-standing open questions for even-hole-free graphs.
Source paper
Tree Independence Number IV. Even-hole-free Graphs
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl · 2024-07-12
https://arxiv.org/abs/2407.08927