← All problems

Esperet's conjecture on polynomially chi-bounded hereditary classes

1 year old · traced to

A graph class is hereditary if it is closed under taking induced subgraphs. It is chi-bounded if there is a function ff such that χ(G)≤f(ω(G))\chi(G)\leq f(\omega(G)) for every graph GG 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.

References

Status

  • Refuted: Marcin Briański, James Davies, Bartosz Walczak. Separating polynomial χ-boundedness from χ-boundedness (Combinatorica, 2023) https://arxiv.org/abs/2201.08814

Source: N. Rahimi and D. A. Mojdeh, “On the analogue of Esperet's conjecture: Characterizing hereditary classes”, arXiv:2512.09176 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.