Induced colorful trees and paths in large chromatic graphs

Gyárfás, András and Sárközy, Gábor (2016) Induced colorful trees and paths in large chromatic graphs. ELECTRONIC JOURNAL OF COMBINATORICS, 23 (4). P4.46. ISSN 1097-1440

Preview

Text 6239_19396_2_PB_u.pdf Download (241kB) | Preview

Abstract

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 Pk on k vertices. The first author proved in 1987 that k-chromatic and triangle-free graphs have a path Pk 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 Pk. 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.

Actions (login required)

Edit Item