Polynomial χ-boundedness for odd-cycle k-multihole graphs

Open problem (poly-χ-bounded for k-multihole with only odd cycles) · arXiv:2202.09118

arXiv Problem medium confidence— first stated 2022-02-18

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Status open high confidence

The source paper (arXiv:2202.09118) establishes polynomial χ-boundedness for graphs with no k-multihole in general, and also for the variant where holes are odd or of length four, but explicitly leaves open the case where all holes have odd length. This class contains {P5, C5}-free graphs, for which the best known bound remains exponential (2^(ω−1)), not polynomial. A broad web search and inspection of the authors' subsequent publication record found no follow-up paper resolving this open problem as of May 2026.

Reviewer notes. The conjecture is closely related to polynomial χ-boundedness of {P5, C5}-free graphs, which is a well-known open problem. The best known bound for {P5, C5}-free graphs is χ(G) ≤ 2^(ω(G)−1) (Chudnovsky–Sivaraman), which is exponential. No follow-up paper resolving or making partial progress specifically on the k-multihole odd-cycle variant was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. For any integer $k \geq 1$, is the class of graphs with no $k$-multihole in which all the cycles have odd length polynomially $\chi$-bounded?

Context

This class is $\chi$-bounded [9], but it contains the class of $\{P_5, C_5\}$-free graphs. The authors state they cannot yet prove it is poly-$\chi$-bounded, referring to [15] for the best current bounds.

Also stated in

Polynomial bounds for chromatic number VII. Disjoint holes (2022-02-18)

Notes. Stated as an open limitation in the introduction; no formal label.

Source paper

Polynomial bounds for chromatic number VII. Disjoint holes
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2022-02-18
https://arxiv.org/abs/2202.09118 PDF source