Skip to main content

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures

Author(s): Chudnovsky, Maria; Seymour, Paul; Scott, Alex

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1ds47
Abstract: Gyarfas conjectured in 1985 that for all $k$, $l$, every graph with no clique of size more than $k$ and no odd hole of length more than $l$ has chromatic number bounded by a function of $k$ and $l$. We prove three weaker statements: (1) Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five; (2) For all $l$, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than $l$; (3) For all $k$, $l$, every graph with no clique of size more than $k$ and sufficiently large chromatic number contains either a 5-hole or a hole of length more than $l$.
Publication Date: May-2016
Electronic Publication Date: 27-Jan-2016
Citation: Chudnovsky, Maria, Seymour, Paul, Scott, Alex. (Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
DOI: 10.1016/j.jctb.2016.01.003
Pages: 109-128
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.