pith. machine review for the scientific record. sign in

arxiv: 2512.24907 · v3 · submitted 2025-12-31 · 🧮 math.CO

Recognition: unknown

Polynomial chi-boundedness for excluding P₅

Authors on Pith no claims yet
classification 🧮 math.CO
keywords chromaticdensitynumberallowsapproachboundedboundednessclique
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Ramsey-type $\chi$-bounds for $\chi$-bounded graph classes

    math.CO 2026-05 unverdicted novelty 8.0

    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.