Coloring Powers of Planar Graphs
Geir Agnarsson, Magnús M. Halldórsson · SIAM Journal on Discrete Mathematics · 2003
We give nontrivial boundsfor 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 $\lceil 9\Delta /5 \rceil$, for the maximum degree $\Delta$ sufficiently large, and that it is sharp. In general, we show for a fixed integer $k\geq1$ the inductiveness, the chromatic number, and the choosability of G k to be $O(\Delta^{\lfloor k/2 \rfloor})$, which is tight.