2-distance 4-colorability of planar subcubic graphs with girth at least 22
Oleg Veniaminovich Borodin, Anna O. Ivanova · Discussiones Mathematicae Graph Theory · 2012
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 ≥ 22.