Forests are multibounding chromatic bound
Conjecture 1.6 · arXiv:2303.11766
Status open high confidence
Conjecture 1.6 from arXiv:2303.11766 — that every forest is multibounding — remains open as of May 2026. The source paper itself established the conjecture for paths and brooms, and earlier work (arXiv:2202.05557) handled trees of radius two; no subsequent paper resolving the full conjecture has been identified in a broad web search covering arXiv, Seymour's publication list, and related follow-up work through 2025.
Reviewer notes. No follow-up paper proving or disproving the full conjecture was found. Known special cases: paths (proved in the source paper), brooms (proved in the source paper), trees of radius two (proved in arXiv:2202.05557 by Scott and Seymour). The conjecture is closely related to the polynomial Gyárfás-Sumner conjecture; any forest satisfying the polynomial-bound Conjecture 1.2 of the same paper is automatically multibounding.
Context
A graph $H$ is multibounding if for every $d \geq 1$ there is a polynomial $f(t)$ such that, for all $t \geq 1$, every $H$-free graph with no $K_d(t)$ subgraph satisfies $\chi(G) \leq f(t)$. Every multibounding graph must be a forest satisfying the Gyárfás-Sumner conjecture, and any forest satisfying the polynomial-bound Conjecture 1.2 is multibounding. The paper establishes that paths, brooms, and disjoint unions of multibounding forests are multibounding, motivating the general conjecture.
Notes. Explicitly introduced with 'We propose: 1.6 Conjecture' in the paper.
Source paper
Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph
Tung Nguyen, Alex Scott, Paul Seymour · 2023-03-21
https://arxiv.org/abs/2303.11766
PDF source