Local colourings of Cartesian product graphs |
| |
Authors: | Sandi Klavžar |
| |
Affiliation: | 1. Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia;2. Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia;3. Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia |
| |
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 |
|
|