Fractionally colouring $P_5$-free graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915702761324544 |
|---|---|
| author | Nguyen, Tung H. |
| author_facet | Nguyen, Tung H. |
| contents | We obtain some $d\ge2$ such that every graph $G$ with no induced copy of the five-vertex path $P_5$ has at most $α(G)ω(G)^d$ vertices. This ``off-diagonal Ramsey'' statement implies that every such graph $G$ has fractional chromatic number at most $ω(G)^d$, and is another step towards the polynomial Gyárfás-Sumner conjecture for $P_5$. The proof uses the recent Erdős-Hajnal result for $P_5$ and adapts a decomposition argument for $P_5$-free graphs developed by the author in an earlier paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05724 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fractionally colouring $P_5$-free graphs Nguyen, Tung H. Combinatorics 05C35, 05C55, 05C69, 05C72 We obtain some $d\ge2$ such that every graph $G$ with no induced copy of the five-vertex path $P_5$ has at most $α(G)ω(G)^d$ vertices. This ``off-diagonal Ramsey'' statement implies that every such graph $G$ has fractional chromatic number at most $ω(G)^d$, and is another step towards the polynomial Gyárfás-Sumner conjecture for $P_5$. The proof uses the recent Erdős-Hajnal result for $P_5$ and adapts a decomposition argument for $P_5$-free graphs developed by the author in an earlier paper. |
| title | Fractionally colouring $P_5$-free graphs |
| topic | Combinatorics 05C35, 05C55, 05C69, 05C72 |
| url | https://arxiv.org/abs/2510.05724 |