Polynomial bounds for chromatic number II: excluding a star-forest
The Gyarfas-Sumner conjecture says that for every forest $H$, there is a function $f$ such that if $G$ is $H$-free then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Louis Esperet conjectured that, whenever such a statement holds, $f$ can be...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Wiley
2022
|
| Subjects: |
| _version_ | 1826309726019780608 |
|---|---|
| author | Scott, A Seymour, P Spirkl, S |
| author_facet | Scott, A Seymour, P Spirkl, S |
| author_sort | Scott, A |
| collection | OXFORD |
| description | The Gyarfas-Sumner conjecture says that for every forest $H$, there is a
function $f$ such that if $G$ is $H$-free then $\chi(G)\le f(\omega(G))$ (where
$\chi, \omega$ are the chromatic number and the clique number of $G$). Louis
Esperet conjectured that, whenever such a statement holds, $f$ can be chosen to
be a polynomial. The Gyarfas-Sumner conjecture is only known to be true for a
modest set of forests $H$, and Esperet's conjecture is known to be true for
almost no forests. For instance, it is not known when $H$ is a five-vertex
path. Here we prove Esperet's conjecture when each component of $H$ is a star. |
| first_indexed | 2024-03-07T07:40:00Z |
| format | Journal article |
| id | oxford-uuid:d54bf7e9-6447-4c4f-adb3-50b81bdac5bd |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:40:00Z |
| publishDate | 2022 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:d54bf7e9-6447-4c4f-adb3-50b81bdac5bd2023-04-04T10:16:41ZPolynomial bounds for chromatic number II: excluding a star-forestJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d54bf7e9-6447-4c4f-adb3-50b81bdac5bdχ-boundednessEnglishSymplectic ElementsWiley2022Scott, ASeymour, PSpirkl, SThe Gyarfas-Sumner conjecture says that for every forest $H$, there is a function $f$ such that if $G$ is $H$-free then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Louis Esperet conjectured that, whenever such a statement holds, $f$ can be chosen to be a polynomial. The Gyarfas-Sumner conjecture is only known to be true for a modest set of forests $H$, and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when $H$ is a five-vertex path. Here we prove Esperet's conjecture when each component of $H$ is a star. |
| spellingShingle | χ-boundedness Scott, A Seymour, P Spirkl, S Polynomial bounds for chromatic number II: excluding a star-forest |
| title | Polynomial bounds for chromatic number II: excluding a star-forest |
| title_full | Polynomial bounds for chromatic number II: excluding a star-forest |
| title_fullStr | Polynomial bounds for chromatic number II: excluding a star-forest |
| title_full_unstemmed | Polynomial bounds for chromatic number II: excluding a star-forest |
| title_short | Polynomial bounds for chromatic number II: excluding a star-forest |
| title_sort | polynomial bounds for chromatic number ii excluding a star forest |
| topic | χ-boundedness |
| work_keys_str_mv | AT scotta polynomialboundsforchromaticnumberiiexcludingastarforest AT seymourp polynomialboundsforchromaticnumberiiexcludingastarforest AT spirkls polynomialboundsforchromaticnumberiiexcludingastarforest |