Journal article
Induced subgraphs of graphs with large chromatic number IX: rainbow paths
- Abstract:
-
We prove that for all integers κ
,s≥0 there exists c with the following property. Let G be a graph with clique number at most κ 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 κ=2 and girth at least five.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 208.3KB, Terms of use)
-
Authors
- Publisher:
- Electronic Journal of Combinatorics
- Journal:
- Electronic Journal of Combinatorics More from this journal
- Volume:
- 24
- Issue:
- 2
- Pages:
- #P2.53
- Publication date:
- 2017-06-30
- Acceptance date:
- 2017-06-22
- EISSN:
-
1097-1440
- Keywords:
- Pubs id:
-
pubs:702716
- UUID:
-
uuid:6c8487b8-dc9a-42b4-a1b6-d089887e58eb
- Local pid:
-
pubs:702716
- Source identifiers:
-
702716
- Deposit date:
-
2017-07-03
- ARK identifier:
Terms of use
- Copyright holder:
- Scott etal
- Copyright date:
- 2017
- Notes:
- This is the version of record of the article. The final version is available online from Electronic Journal of Combinatorics at: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p53
If you are the owner of this record, you can report an update to it here: Report update to this record