Local colorings of graphs

Abstract

A local coloring of a graph G of order at least 2 is a function c : V(G) → N having the property that for each set S ⊆ V(G) with 2 ≤ |S| ≤ 3, there exist vertices u,v ∈ S such that |c(u) - c(v)| ≥ m _S, where m_S is the size of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by X_l(c). The local chromatic number of G is X_l(G) = min{X_l(c)}, where the minimum is taken over all local colorings c of G. The local chromatic numbers of all complete multipartite graphs are determined.