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

Full metadata record

DC Field	Value	Language
dc.contributor.author	Scott, Alex	-
dc.contributor.author	Seymour, Paul D.	-
dc.date.accessioned	2018-07-20T15:11:11Z	-
dc.date.available	2018-07-20T15:11:11Z	-
dc.date.issued	2017	en_US
dc.identifier.citation	Scott, Alex, Seymour, Paul. (2017). Induced subgraphs of graphs with large chromatic number IX: Rainbow paths. ELECTRONIC JOURNAL OF COMBINATORICS, 24	en_US
dc.identifier.issn	1077-8926	-
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr1jd68	-
dc.description.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.	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	ELECTRONIC JOURNAL OF COMBINATORICS	en_US
dc.rights	Final published version. This is an open access article.	en_US
dc.title	Induced subgraphs of graphs with large chromatic number IX: Rainbow paths	en_US
dc.type	Journal Article	en_US
dc.date.eissued	2017-06-30	en_US
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article	en_US

Files in This Item:

File	Description	Size	Format
6768-21253-2-PB.pdf		208.33 kB	Adobe PDF	View/Download