For graphs with no induced T (forest with broom components or any forest) and no induced H (complete multipartite or bipartite), χ(G) is at most C times R(α(H), ω(G)+1) for a constant C depending only on T and H.
Polynomial $\chi$-boundedness for excluding $P_5$
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Resolving a 1985 open problem of Gy\'arf\'as, we prove that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path $P_5$. Our approach introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erd\H{o}s-Hajnal result for $P_5$.
fields
math.CO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Ramsey-type $\chi$-bounds for $\chi$-bounded graph classes
For graphs with no induced T (forest with broom components or any forest) and no induced H (complete multipartite or bipartite), χ(G) is at most C times R(α(H), ω(G)+1) for a constant C depending only on T and H.