Local coloring of Kneser graphs

A local coloring of a graph GG is a function c:V(G)→Nc:V(G)→N having the property that for each set S⊆V(G)S⊆V(G) with 2≤|S|≤32≤|S|≤3, there exist vertices u,v∈Su,v∈S such that |c(u)−c(v)|≥mS|c(u)−c(v)|≥mS, where mSmS is the number of edges of the induced subgraph 〈S〉〈S〉. The maximum color assigned by a local coloring cc to a vertex of GG is called the value of cc and is denoted by χℓ(c)χℓ(c). The local chromatic number of GG is χℓ(G)=min{χℓ(c)}χℓ(G)=min{χℓ(c)}, where the minimum is taken over all local colorings cc of GG. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207–221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k)K(n,k) for some values of nn and kk is determined.