Square Coloring of Planar Graphs with Maximum Degree at Most Five

Abstract

The \textit{square} of a graph $G$, denoted by $G^2$, is obtained from $G$ by adding an edge to connect every pair of vertices with a common neighbor in $G$. In this paper we prove that for every planar graph $G$ with maximum degree at most $5$, $G^2$ admits a proper vertex coloring using at most $17$ colors, which improves the upper bound $18$ recently obtained by Hou, Jin, Miao, and Zhao.

This is the second version. The preliminary version is uploaded to arxiv on Augest 2nd. After completing this paper, we learned that Kengo Aoki also proved the main result of this paper independently in arXiv:2307.16394