Locally rainbow graphs
Abstract
A local coloring of a graph G is a function c: V(G) → N having the property that for each set S ⊆ V(G) with 2 ≤ |S| ≤ 3, there exist vertices υ,μ ∈ S such that |c(u) - c(μ)| ≥ ms, where ms 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 χℓ(c)-The local chromatic number of G is χ ℓ(G) = min{Xe(c)}, where the minimum is taken over all local coloring c of G. If χℓ(c) = χℓ(G), then c is called a minimum local coloring of G.A. graph G is called locally rainbow if every minimum local coloring of G uses all of the colors 1,2,..., χℓ(G). The concept of local coloring of graphs introduced by Chartrand et. al. in 2003. They suggested a conjecture on locally rainbow graphs. In this paper it is shown that their conjecture is true and for a given positive integer k, there exists a locally rainbow graph Rk with χℓ(Rk) = k.
