Local colourings of Cartesian product graphs

Abstract

A local colouring of a graph G is a function c: V(G)→ℕ 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 colour assigned by c is the value χ_ℓ(c) of c, and the local chromatic number of G is χ_ℓ(G)=min {χ_ℓ(c): c is a local colouring of G}. In this note the local chromatic number is determined for Cartesian products G □ H, where G and GH are 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that if G and H are graphs such that χ(G)≤⌊ χ_ℓ(H)/2 ⌋, then χ_ℓ(G □ H)≤χ_ℓ(H)+1.

Keywords:

• local chromatic number
• chromatic number
• Cartesian product

2010 AMS Subject Classifications::

• 05C15
• 05C76

Acknowledgements

This work was supported in part by ARRS Slovenia under the grant P1-0297, by the National Natural Science Foundation of China under the grant 61309015.