Induced Subgraphs of Graphs with Large Chromatic Number IX: Rainbow Paths
Induced Subgraphs of Graphs with Large Chromatic Number IX: Rainbow Paths
复制标题
DOI：
10.37236/6768
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
A. Scott;P. Seymour
中科院分区：
文献类型：
--
作者：
A. Scott;P. Seymour
我们证明了对于所有非负整数k，s存在c，它具有如下性质。设G为团数不超过k且色数大于c的图，则对于G的每个顶点着色（不一定是最优的），G的某个诱导子图是s顶点路径，并且其所有顶点具有不同的颜色。这扩展了Gyarfas和Sarkozy最近的一个结果，他们证明了同样的结果（当k=2时）对于周长至少为5的图G。
We prove that for all nonnegative integers k,s 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, who proved the same (when k=2) for graphs G with girth at least five.