Coloring Powers of Planar Graphs (Algorithm Engineering as a New Paradigm)
Geir Agnarsson, Magnús M. Halldórsson · Kyoto University Research Information Repository (Kyoto University) · 1999
We give nontrivial bounds for the chromatic number of power graphs $G^{k}$ of a planar graph $G$ .In particular, we show that they can be colored with $O(\triangle^{\mathrm{L}^{k/\rfloor}}2)$ colors, which is best possible, and give 2-approximation for square graphs and $O(1)$ -approximation for cubic graphs.