Polynomial χ-bounds for forest-free graphs

About 1 year old · traced to

Let HH be a forest, and let GG be an HH-free graph, meaning that GG has no induced subgraph isomorphic to HH. Write χ(G)\chi(G) for its chromatic number and ω(G)\omega(G) for its clique number. Polynomial χ-bound conjecture for forest-free graphs. There exists a constant c>0c>0, depending on HH, such that

χ(G)≤ω(G)c\chi(G)\leq \omega(G)^c

for every HH-free graph GG. This conjecture is presented as a consequence of combining the Gyárfás–Sumner conjecture with Esperet's conjecture; the supplied text does not state whether it has been resolved.

References

Primary source

N. Rahimi and D. A. Mojdeh, “Towards Esperet's Conjecture: Polynomial χ-Bounds for Structured Graph Classes”, arXiv:2512.09186 (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.