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

Author: 

Scott, A
Seymour, P

Publication Date: 

1 November 2016

Journal: 

Journal of Combinatorial Theory. Series B

Last Updated: 

2019-12-12T09:00:30.34+00:00

Volume: 

121

DOI: 

10.1016/j.jctb.2015.10.002

page: 

68-84

abstract: 

© 2015 Elsevier Inc.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.

Symplectic id: 

632956

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article