Cliques in squares of graphs with maximum average degree less than 4.

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