Abstract
Consider a graph G = (V, E) and, for each vertex v is an element of V. a subset Sigma(v) of neighbors of v. A Sigma-coloring is a coloring of the elements of V so that vertices appearing together in some E(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 Sigma(v), denoted by rho(Sigma). In this paper we study graph classes F for which there is a function f, such that for any graph G is an element of F and any Sigma, there is a Sigma-coloring using at most f (rho(Sigma)) colors.
It is proved that if such a function exists for a class F, then f 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.