Recognition: unknown
Polynomial chi-boundedness for excluding P₅
classification
🧮 math.CO
keywords
chromaticdensitynumberallowsapproachboundedboundednessclique
read the original 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$.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.