Polynomial $χ$-boundedness for excluding $P_5$
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917480337768448 |
|---|---|
| author | Nguyen, Tung H. |
| author_facet | Nguyen, Tung H. |
| contents | Resolving a 1985 open problem of Gyárfás, 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ős-Hajnal result for $P_5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24907 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial $χ$-boundedness for excluding $P_5$ Nguyen, Tung H. Combinatorics 05C15, 05C35, 05C55, 05C69, 05C75, 05C85, 68R10 Resolving a 1985 open problem of Gyárfás, 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ős-Hajnal result for $P_5$. |
| title | Polynomial $χ$-boundedness for excluding $P_5$ |
| topic | Combinatorics 05C15, 05C35, 05C55, 05C69, 05C75, 05C85, 68R10 |
| url | https://arxiv.org/abs/2512.24907 |