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

Alex Scott; Paul Seymour

doi:10.37236/6768

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

Alex Scott, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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 Gyárfás and Sárközy (2016), who proved the same for graphs G with k = 2 and girth at least five.

Original language	English (US)
Article number	#P2.53
Journal	Electronic Journal of Combinatorics
Volume	24
Issue number	2
DOIs	https://doi.org/10.37236/6768
State	Published - Jun 30 2017

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Keywords

Colouring
Rainbow

Access to Document

10.37236/6768

Cite this

@article{8973e353b76e4ccebbc8eedf952bffcd,

title = "Induced subgraphs of graphs with large chromatic number IX: Rainbow paths",

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 Gy{\'a}rf{\'a}s and S{\'a}rk{\"o}zy (2016), who proved the same for graphs G with k = 2 and girth at least five.",

keywords = "Colouring, Rainbow",

author = "Alex Scott and Paul Seymour",

year = "2017",

month = jun,

day = "30",

doi = "10.37236/6768",

language = "English (US)",

volume = "24",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2",

}

TY - JOUR

T1 - Induced subgraphs of graphs with large chromatic number IX

T2 - Rainbow paths

AU - Scott, Alex

AU - Seymour, Paul

PY - 2017/6/30

Y1 - 2017/6/30

N2 - 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.

AB - 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.

KW - Colouring

KW - Rainbow

UR - http://www.scopus.com/inward/record.url?scp=85021649880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85021649880&partnerID=8YFLogxK

U2 - 10.37236/6768

DO - 10.37236/6768

M3 - Article

AN - SCOPUS:85021649880

SN - 1077-8926

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - #P2.53

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this