Induced subgraphs of graphs with large chromatic number. XI. Orientations

Author: 

Chudnovsky, M
Scott, A
Seymour, P

Publication Date: 

February 2019

Journal: 

EUROPEAN JOURNAL OF COMBINATORICS

Last Updated: 

2019-04-28T03:49:31.673+01:00

Issue: 

2

Volume: 

76

DOI: 

10.1016/j.ejc.2018.09.003

page: 

53-61

abstract: 

© 2017, Australian National University. All rights reserved. We prove that for all integers k, s ≥ 0 there exists c with the following property. Let G be a graph with clique number at most k and chromatic number more than c. Then for every vertex-colouring (not necessarily optimal) of G, some induced subgraph of G is an s-vertex path, and all its vertices have different colours. This extends a recent result of Gyárfás and Sárközy (2016), who proved the same for graphs G with k = 2 and girth at least five.

Symplectic id: 

702716

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article