Induced subgraphs of graphs with large chromatic number. I. Odd holes
An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture.
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2015
|
| _version_ | 1797088118828957696 |
|---|---|
| author | Scott, A Seymour, P |
| author_facet | Scott, A Seymour, P |
| author_sort | Scott, A |
| collection | OXFORD |
| description | An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture. |
| first_indexed | 2024-03-07T02:45:21Z |
| format | Journal article |
| id | oxford-uuid:abdeb96f-58c7-4774-8ded-cb6fba701e2b |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:45:21Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:abdeb96f-58c7-4774-8ded-cb6fba701e2b2022-03-27T03:24:55ZInduced subgraphs of graphs with large chromatic number. I. Odd holesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:abdeb96f-58c7-4774-8ded-cb6fba701e2bSymplectic Elements at OxfordElsevier2015Scott, ASeymour, PAn odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture. |
| spellingShingle | Scott, A Seymour, P Induced subgraphs of graphs with large chromatic number. I. Odd holes |
| title | Induced subgraphs of graphs with large chromatic number. I. Odd holes |
| title_full | Induced subgraphs of graphs with large chromatic number. I. Odd holes |
| title_fullStr | Induced subgraphs of graphs with large chromatic number. I. Odd holes |
| title_full_unstemmed | Induced subgraphs of graphs with large chromatic number. I. Odd holes |
| title_short | Induced subgraphs of graphs with large chromatic number. I. Odd holes |
| title_sort | induced subgraphs of graphs with large chromatic number i odd holes |
| work_keys_str_mv | AT scotta inducedsubgraphsofgraphswithlargechromaticnumberioddholes AT seymourp inducedsubgraphsofgraphswithlargechromaticnumberioddholes |