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

Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

3 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 languageEnglish (US)
Article number#P2.53
JournalElectronic Journal of Combinatorics
Volume24
Issue number2
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number IX: Rainbow paths'. Together they form a unique fingerprint.

Cite this