In a proper vertex coloring of a graph a subgraph is colorful if its vertices are colored with different colors. It is well-known (see for example in Gyárfás (1980)) that in every proper coloring of a $k$-chromatic graph there is a colorful path $P_k$ on $k$ vertices. The first author proved in 1987 that $k$-chromatic and triangle-free graphs have a path $P_k$ which is an induced subgraph. N.R. Aravind conjectured that these results can be put together: in every proper coloring of a $k$-chromatic triangle-free graph, there is an induced colorful $P_k$. Here we prove the following weaker result providing some evidence towards this conjecture: For a suitable function $f(k)$, in any proper coloring of an $f(k)$-chromatic graph of girth at least five, there is an induced colorful path on $k$ vertices.
@article{10_37236_6239,
author = {Andras Gyarfas and Gabor Sarkozy},
title = {Induced colorful trees and paths in large chromatic graphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {4},
doi = {10.37236/6239},
zbl = {1353.05049},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6239/}
}
TY - JOUR
AU - Andras Gyarfas
AU - Gabor Sarkozy
TI - Induced colorful trees and paths in large chromatic graphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/6239/
DO - 10.37236/6239
ID - 10_37236_6239
ER -
%0 Journal Article
%A Andras Gyarfas
%A Gabor Sarkozy
%T Induced colorful trees and paths in large chromatic graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6239/
%R 10.37236/6239
%F 10_37236_6239
Andras Gyarfas; Gabor Sarkozy. Induced colorful trees and paths in large chromatic graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 4. doi: 10.37236/6239
