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


2-Distance 4-coloring of planar subcubic graphs
Authors:O. V. Borodin  A. O. Ivanova
Affiliation:1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Novosibirsk State University,Novosibirsk,Russia;3.Institute of Mathematics at Yakutsk State University,Yakutsk State University,Yakutsk,Russia
Abstract:The trivial lower bound for the 2-distance chromatic number χ 2(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ 2 = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ 2(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 23, which strengthens a similar result by O. V. Borodin, A. O. Ivanova, and T. K. Neustroeva (2004) and Z. Dvořák, R. Škrekovski, and M. Tancer (2008) for g ≥ 24.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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