Induced subgraphs of graphs with large chromatic number. I. Odd holes
Author(s): Scott, Alex; Seymour, Paul D.
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1ct0m| Abstract: | An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyarfas 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. (C) 2015 Elsevier Inc. All rights reserved. |
| Publication Date: | Nov-2016 |
| Electronic Publication Date: | 30-Oct-2015 |
| Citation: | Scott, Alex, Seymour, Paul. (2016). Induced subgraphs of graphs with large chromatic number. I. Odd holes. JOURNAL OF COMBINATORIAL THEORY SERIES B, 121 (68 - 84. doi:10.1016/j.jctb.2015.10.002 |
| DOI: | doi:10.1016/j.jctb.2015.10.002 |
| ISSN: | 0095-8956 |
| EISSN: | 1096-0902 |
| Pages: | 68 - 84 |
| Language: | English |
| Type of Material: | Journal Article |
| Journal/Proceeding Title: | JOURNAL OF COMBINATORIAL THEORY SERIES B |
| Version: | Author's manuscript |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.