Coloring the square of a planar graph
Jan van den Heuvel, Sean R. McGuinness · Journal of Graph Theory · 2002
Abstract We prove that for any planar graph G with maximum degree Δ, it holds that the chromatic number of the square of G satisfies χ(G2) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 110–124, 2003