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 等数据库收录! |
|