Skip to main content

Induced subgraphs of graphs with large chromatic number. I. Odd holes

Author(s): Scott, Alex; Seymour, Paul D

Download
To 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.