Skip to main content

Induced subgraphs of graphs with large chromatic number IX: Rainbow paths

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1jd68
Abstract: 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 Gyarfas and Sarkozy (2016), who proved the same for graphs G with K = 2 and girth at least five.
Publication Date: 2017
Electronic Publication Date: 30-Jun-2017
Citation: Scott, Alex, Seymour, Paul. (2017). Induced subgraphs of graphs with large chromatic number IX: Rainbow paths. ELECTRONIC JOURNAL OF COMBINATORICS, 24
ISSN: 1077-8926
Type of Material: Journal Article
Journal/Proceeding Title: ELECTRONIC JOURNAL OF COMBINATORICS
Version: Final published version. This is an open access article.



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.