Distance-two coloring of sparse graphs

Consider a graph G=(V,E)G=(V,E) and, for each vertex v∈Vv∈V, a subset Σ(v)Σ(v) of neighbors of vv. A ΣΣ-coloring is a coloring of the elements of VV so that vertices appearing together in some Σ(v)Σ(v) receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set Σ(v)Σ(v), denoted by ρ(Σ)ρ(Σ). In this paper we study graph classes FF for which there is a function ff, such that for any graph G∈FG∈F and any ΣΣ, there is a ΣΣ-coloring using at most f(ρ(Σ))f(ρ(Σ)) colors. It is proved that if such a function exists for a class FF, then ff can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes.