
arXiv: 1702.01094
We prove that for all integers $\kappa, s\ge 0$ there exists $c$ with the following property. Let $G$ be a graph with clique number at most $\kappa$ 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 $\kappa=2$ and girth at least five.
colouring, Coloring of graphs and hypergraphs, rainbow, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles
colouring, Coloring of graphs and hypergraphs, rainbow, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
