Polynomial degree-bounding for hereditary degree-bounded classes

Polynomial degree-bounding function for hereditary degree-bounded classes · arXiv:2307.08361

arXiv Problem medium confidence— first stated 2023-11-01

Authors: Xiying Du, António Girão, Zach Hunter, Rose McCarty, Alex Scott

Status solved high confidence

The conjecture was answered affirmatively by Girão and Hunter in a 2025 paper in the International Mathematics Research Notices, which proves that every hereditary degree-bounded class has a polynomial degree-bounding function, fully resolving the question left open in arXiv:2307.08361. A related earlier result by Bourneuf, Bucćić, Cook, and Davies (arXiv:2311.03341, published in Advances in Combinatorics 2024) proved polynomial bounds for hereditary classes defined by excluding induced subdivisions of a fixed graph, establishing a key step toward the full result.

Cited literature (2)

partial On polynomial degree-boundedness (2024)

Romain Bourneuf, Matija Bucćić, Linda Cook, James Davies · Advances in Combinatorics · arXiv:2311.03341

Proves that for every graph H there is a polynomial p such that every graph of average degree at least p(s) contains either K_{s,s} or an induced subdivision of H, establishing polynomial bounds for hereditary degree-bounded classes defined by forbidden induced subdivisions.
proof Induced Subdivisions in $K_{s,s}$-Free Graphs With Polynomial Average Degree (2025)

António Girão, Zach Hunter · International Mathematics Research Notices · doi:10.1093/imrn/rnaf025

Proves that every hereditary degree-bounded class has a polynomial degree-bounding function, fully resolving the open question from arXiv:2307.08361.

Reviewer notes. The conjecture is solved: Girão and Hunter (IMRN 2025, DOI 10.1093/imrn/rnaf025) proved polynomial bounds suffice for every hereditary degree-bounded class. The arXiv preprint ID for the Girão-Hunter paper was not found in the sources consulted. The internal reference arXiv:2508.14332 is a false corpus match unrelated to this conjecture. The survey arXiv:2403.05737 (Girão, Hunter, 2024) provides additional context on the degree-boundedness landscape.

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

Problem. Is there always a polynomial degree-bounding function for every hereditary degree-bounded class of graphs? That is, for every hereditary degree-bounded class $\mathcal{F}$, does there exist a polynomial $g$ such that $d(G) \leq g(\tau(G))$ for every $G \in \mathcal{F}$?

Context

Corollary 1.4 establishes that every hereditary degree-bounded class admits an exponential degree-bounding function of the form $C^{s^3}$, which is the first bound of any type on the rate of growth. The paper notes explicitly in both the abstract and the introduction that it is open whether a polynomial always suffices. The analogous question for $\chi$-boundedness has a negative answer (Briański, Davies, and Walczak).

Notes. Stated in prose in the abstract and in the introduction without a labelled theorem environment.

Source paper

Induced $C_4$-free subgraphs with large average degree
Xiying Du, António Girão, Zach Hunter, Rose McCarty, Alex Scott · 2023-11-01
https://arxiv.org/abs/2307.08361 PDF source