Injective (Δ + 1)-coloring of planar graphs with girth 6
Oleg Veniaminovich Borodin, Anna O. Ivanova · Siberian Mathematical Journal · 2011
A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ i = Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ i ≤ Δ + 1.