Improved square coloring of planar graphs

Abstract

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac{3}{2}\Delta +1$ colors are sufficient to square color every planar graph of maximum degree $\Delta$. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2\Delta +7$ colors are sufficient, which improves the best known bounds when $6⩽\Delta ⩽31$.

14 pages, 8 figures