Bounding Clique Size in Squares of Planar Graphs

Wegner conjectured that if $G$ is a planar graph with maximum degree $\mathrm{\Delta }\ge 8$, then $\chi (G^2)\le \lfloor \frac{3}{2}\mathrm{\Delta }\rfloor +1$. This problem has received much attention, but remains open for all $\mathrm{\Delta }\ge 8$. Here we prove an analogous bound on $\omega (G^2)$: If $G$ is a plane graph with $\mathrm{\Delta }(G)\ge 36$, then $\omega (G^2)\le \lfloor \frac{3}{2}\mathrm{\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 $\mathrm{\Delta }(G)\ge 19$ and $S$ is a maximal clique in $G^2$ with $\mathrm{\mid }S\mathrm{\mid }\ge \mathrm{\Delta }(G)+20$, then there exist $x,y,z\in V(G)$ such that $S=\{w:\mathrm{\mid }N[w]\cap \{x,y,z\}\mathrm{\mid }\ge 2\}$.