Cliques in Squares of Graphs with Maximum Average Degree less than 4

Abstract

Hocquard, Kim, and Pierron constructed, for every even integer $D\ge 2$, a 2-degenerate graph $G_D$ with maximum degree $D$ such that $\omega (G_D^2)=\frac{5}{2}D$. We prove for (a) all 2-degenerate graphs $G$ and (b) all graphs $G$ with $\mbox{mad}(G)<4$, upper bounds on the clique number $\omega (G^2)$ of $G^2$ that match the lower bound given by this construction, up to small additive constants. We show that if $G$ is 2-degenerate with maximum degree $D$, then $\omega (G^2)\le \frac{5}{2}D+72$ (with $\omega (G^2)\le \frac{5}{2}D+60$ when $D$ is sufficiently large). And if $G$ has $\mbox{mad}(G)<4$ and maximum degree $D$, then $\omega (G^2)\le \frac{5}{2}D+532$. Thus, the construction of Hocquard et al. is essentially best possible. Our proofs introduce a "token passing" technique to derive crucial information about non-adjacencies in $G$ of vertices that are adjacent in $G^2$. This is a powerful technique for working with such graphs that has not previously appeared in the literature.

15 pages, 7 figures; final version incorporates minor reviewer feedback; to appear in J. Graph Theory