首页 | 本学科首页   官方微博 | 高级检索  
     


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, vS 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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号