2-Distance 4-coloring of planar subcubic graphs
Oleg Veniaminovich Borodin, Anna O. Ivanova · Journal of Applied and Industrial Mathematics · 2011
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.