Bounding Clique Size in Squares of Planar Graphs

Abstract

Wegner conjectured that if $G$ is a planar graph with maximum degree $\Delta \ge 8$, then $\chi (G^2)\le \lfloor \frac{3}{2}\Delta \rfloor +1$. This problem has received much attention, but remains open for all $\Delta \ge 8$. Here we prove an analogous bound on $\omega (G^2)$: If $G$ is a plane graph with $\Delta (G)\ge 36$, then $\omega (G^2)\le \lfloor \frac{3}{2}\Delta (G)\rfloor +1$. In fact, this is a corollary of the following lemma, which is our main result. If $G$ is a plane graph with $\Delta (G)\ge 19$ and $S$ is a maximal clique in $G^2$ with $|S|\ge \Delta (G)+20$, then there exist $x,y,z\in V(G)$ such that $S=\{w:|N[w]\cap \{x,y,z\}|\ge 2\}$.

7 pages, 5 figures, 2nd version incorporates minor reviewer feedback, to appear in European Journal of Combinatorics