Esperet's conjecture on polynomially chi-bounded hereditary classes
Esperet's conjecture on polynomially chi-bounded hereditary classes
A graph class is hereditary if it is closed under taking induced subgraphs. It is chi-bounded if there is a function such that for every graph in the class, and it is poly-chi-bounded if such a function can be chosen to be a polynomial.
Esperet's conjecture. Every chi-bounded hereditary class is poly-chi-bounded.
The source states that this conjecture was recently disproved; the current question is to identify which hereditary classes are poly-chi-bounded.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
N. Rahimi and D. A. Mojdeh, “On the analogue of Esperet's conjecture: Characterizing hereditary classes”, arXiv:2512.09176 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.