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

Daniel W. Cranston, Gexin Yu

Published 2023-05-19Version 1

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)=\frac52D$. They asked whether (a) there exists $D_0$ such that every 2-degenerate graph $G$ with maximum degree $D\ge D_0$ satisfies $\chi(G^2)\le \frac52D$ and (b) whether this result holds more generally for every graph $G$ with mad(G)<4. In this direction, we prove 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 \frac52D+72$ (with $\omega(G^2)\le \frac52D+60$ when $D$ is sufficiently large). And if $G$ has mad(G)<4 and maximum degree $D$, then $\omega(G^2)\le \frac52D+532$. Thus, the construction of Hocquard et al. is essentially best possible.