Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph with clique number $\omega\ge 3$ has chromatic number at most $\omega^{\log_2(\omega)}$. The best previous result was an exponential upper bound $(5/27)3^{\omega}$, due to Esperet, Lemoine, Maffray, a...
| Egile Nagusiak: | , , |
|---|---|
| Formatua: | Journal article |
| Hizkuntza: | English |
| Argitaratua: |
Springer
2023
|
| _version_ | 1826311015844806656 |
|---|---|
| author | Scott, A Seymour, P Spirkl, S |
| author_facet | Scott, A Seymour, P Spirkl, S |
| author_sort | Scott, A |
| collection | OXFORD |
| description | A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph with clique number $\omega\ge 3$ has chromatic number at most $\omega^{\log_2(\omega)}$. The best previous result was an exponential upper bound $(5/27)3^{\omega}$, due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for $P_5$, which is the smallest open case. Thus there is great interest in whether there is a polynomial bound for $P_5$-free graphs, and our result is an attempt to approach that. |
| first_indexed | 2024-03-07T08:02:09Z |
| format | Journal article |
| id | oxford-uuid:74f4d6c7-7402-4a83-9582-ce15ad5bca20 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:02:09Z |
| publishDate | 2023 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:74f4d6c7-7402-4a83-9582-ce15ad5bca202023-10-09T10:40:06ZPolynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex pathJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:74f4d6c7-7402-4a83-9582-ce15ad5bca20EnglishSymplectic ElementsSpringer2023Scott, ASeymour, PSpirkl, SA graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph with clique number $\omega\ge 3$ has chromatic number at most $\omega^{\log_2(\omega)}$. The best previous result was an exponential upper bound $(5/27)3^{\omega}$, due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for $P_5$, which is the smallest open case. Thus there is great interest in whether there is a polynomial bound for $P_5$-free graphs, and our result is an attempt to approach that. |
| spellingShingle | Scott, A Seymour, P Spirkl, S Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path |
| title | Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path |
| title_full | Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path |
| title_fullStr | Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path |
| title_full_unstemmed | Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path |
| title_short | Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path |
| title_sort | polynomial bounds for chromatic number iv a near polynomial bound for excluding the five vertex path |
| work_keys_str_mv | AT scotta polynomialboundsforchromaticnumberivanearpolynomialboundforexcludingthefivevertexpath AT seymourp polynomialboundsforchromaticnumberivanearpolynomialboundforexcludingthefivevertexpath AT spirkls polynomialboundsforchromaticnumberivanearpolynomialboundforexcludingthefivevertexpath |