On r-hued colorings of graphs without short induced paths

摘要

For integers k, r > 0, a (k, r)-coloring of a graph G is a proper coloring on the vertices of G with k colors such that every vertex nu of degree d(nu) is adjacent to vertices with at least min(d(nu), r} different colors. The r-hued chromatic number, denoted by chi(r) (G), is the smallest integer k for which a graph G has a (k, r)-coloring. We prove the following: