Coloring powers of planar graphs

We give nontrivial bounds for the inductiveness or degeneracy of power graphs G(k) of a planar graph G. This implies bounds for the chromatic number as well, since the inductiveness naturally relates to a greedy algorithm for vertex-coloring the given graph. The inductiveness moreover yields bounds for the choosability of the graph. We show that the inductiveness of a square of a planar graph G is at most [9Delta/ 5], for the maximum degree Delta sufficiently large, and that it is sharp. In general, we show for a fixed integer k greater than or equal to 1 the inductiveness, the chromatic number, and the choosability of G(k) to be O(Delta([k/2)]), which is tight.