Polynomial bounds for chromatic number III: excluding a double star
A double star is a tree with two internal vertices. It is known that the Gy\'arf\'as-Sumner conjecture holds for double stars, that is, for every double star $H$, there is a function $f$ such that if $G$ does not contain $H$ as an induced subgraph then $\chi(G)\le f(\omega(G))$ (where $\ch...
| Asıl Yazarlar: | , , |
|---|---|
| Materyal Türü: | Journal article |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
Wiley
2022
|
| _version_ | 1826309673801744384 |
|---|---|
| author | Scott, A Seymour, P Spirkl, S |
| author_facet | Scott, A Seymour, P Spirkl, S |
| author_sort | Scott, A |
| collection | OXFORD |
| description | A double star is a tree with two internal vertices. It is known that the
Gy\'arf\'as-Sumner conjecture holds for double stars, that is, for every double
star $H$, there is a function $f$ such that if $G$ does not contain $H$ as an
induced subgraph then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the
chromatic number and the clique number of $G$). Here we prove that $f$ can be
chosen to be a polynomial. |
| first_indexed | 2024-03-07T07:37:52Z |
| format | Journal article |
| id | oxford-uuid:5aeebcb9-5925-49e0-bd1e-b3d5916e0b1e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:37:52Z |
| publishDate | 2022 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:5aeebcb9-5925-49e0-bd1e-b3d5916e0b1e2023-04-04T07:39:43ZPolynomial bounds for chromatic number III: excluding a double starJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5aeebcb9-5925-49e0-bd1e-b3d5916e0b1eEnglishSymplectic ElementsWiley2022Scott, ASeymour, PSpirkl, SA double star is a tree with two internal vertices. It is known that the Gy\'arf\'as-Sumner conjecture holds for double stars, that is, for every double star $H$, there is a function $f$ such that if $G$ does not contain $H$ as an induced subgraph then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Here we prove that $f$ can be chosen to be a polynomial. |
| spellingShingle | Scott, A Seymour, P Spirkl, S Polynomial bounds for chromatic number III: excluding a double star |
| title | Polynomial bounds for chromatic number III: excluding a double star |
| title_full | Polynomial bounds for chromatic number III: excluding a double star |
| title_fullStr | Polynomial bounds for chromatic number III: excluding a double star |
| title_full_unstemmed | Polynomial bounds for chromatic number III: excluding a double star |
| title_short | Polynomial bounds for chromatic number III: excluding a double star |
| title_sort | polynomial bounds for chromatic number iii excluding a double star |
| work_keys_str_mv | AT scotta polynomialboundsforchromaticnumberiiiexcludingadoublestar AT seymourp polynomialboundsforchromaticnumberiiiexcludingadoublestar AT spirkls polynomialboundsforchromaticnumberiiiexcludingadoublestar |