Induced subgraphs of graphs with large chromatic number. XIII. New brooms
Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree , the class of graphs not containing as an induced subgraph is -bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees...
| Κύριοι συγγραφείς: | , |
|---|---|
| Μορφή: | Journal article |
| Γλώσσα: | English |
| Έκδοση: |
Elsevier
2019
|
| _version_ | 1826260462228996096 |
|---|---|
| author | Scott, A Seymour, P |
| author_facet | Scott, A Seymour, P |
| author_sort | Scott, A |
| collection | OXFORD |
| description | Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree , the class of graphs not containing as an induced subgraph is -bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees , but has been proved for some particular trees. For , let us say a broom of length is a tree obtained from a -edge path with ends by adding some number of leaves adjacent to , and we call its handle. A tree obtained from brooms of lengths by identifying their handles is a -multibroom. Kierstead and Penrice (1994) proved that every -multibroom satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for -multibrooms. In this paper we give a common generalization; we prove that every -multibroom satisfies the Gyárfás-Sumner conjecture. |
| first_indexed | 2024-03-06T19:06:01Z |
| format | Journal article |
| id | oxford-uuid:15286f4e-f468-4357-942c-0360c9fbc9c6 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:06:01Z |
| publishDate | 2019 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:15286f4e-f468-4357-942c-0360c9fbc9c62022-03-26T10:23:56ZInduced subgraphs of graphs with large chromatic number. XIII. New broomsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:15286f4e-f468-4357-942c-0360c9fbc9c6EnglishSymplectic Elements at OxfordElsevier2019Scott, ASeymour, PGyárfás (1975) and Sumner (1981) independently conjectured that for every tree , the class of graphs not containing as an induced subgraph is -bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees , but has been proved for some particular trees. For , let us say a broom of length is a tree obtained from a -edge path with ends by adding some number of leaves adjacent to , and we call its handle. A tree obtained from brooms of lengths by identifying their handles is a -multibroom. Kierstead and Penrice (1994) proved that every -multibroom satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for -multibrooms. In this paper we give a common generalization; we prove that every -multibroom satisfies the Gyárfás-Sumner conjecture. |
| spellingShingle | Scott, A Seymour, P Induced subgraphs of graphs with large chromatic number. XIII. New brooms |
| title | Induced subgraphs of graphs with large chromatic number. XIII. New brooms |
| title_full | Induced subgraphs of graphs with large chromatic number. XIII. New brooms |
| title_fullStr | Induced subgraphs of graphs with large chromatic number. XIII. New brooms |
| title_full_unstemmed | Induced subgraphs of graphs with large chromatic number. XIII. New brooms |
| title_short | Induced subgraphs of graphs with large chromatic number. XIII. New brooms |
| title_sort | induced subgraphs of graphs with large chromatic number xiii new brooms |
| work_keys_str_mv | AT scotta inducedsubgraphsofgraphswithlargechromaticnumberxiiinewbrooms AT seymourp inducedsubgraphsofgraphswithlargechromaticnumberxiiinewbrooms |