Research Article Local colorings of Cartesian product graphs
Zehui Shao · 2014
A local coloring of a graph G is a function c : V (G) → N such that for each S ⊆ V (G), 2 ≤ |S| ≤ 3, there exist u, v ∈ S with |c(u) − c(v)| at least the number of edges in the subgraph induced by S. The maximum color assigned by c is the value χl(c) of c, and the local chromatic number of G is χl(G) = min{χl(c) : c is a local coloring of G}. In this note the local chromatic number is determined for Cartesian products G H, where G and GH are 3-colorable graphs. This result in part corrects an error from [Omoomi, Pourmiri, On the local colorings of graphs, Ars Combin. 86 (2008) 147{159]. It is also proved that if G and H are graphs such that χ(G) ≤ ⌊χl(H)/2⌋, then χl(G H) ≤ χl(H) + 1.