Tight upper bound on the clique size in the square of 2-degenerate graphs

Abstract

The {\em square} of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. In general, $\Delta (G)+1\le \chi (G^2)\le \Delta (G{)}^2+1$ for every graph $G$. Charpentier [1] asked whether $\chi (G^2)\le 2\Delta (G)$ if $mad(G)<4$. But Hocquard, Kim, and Pierron [6] answered his question negatively. For every even value of $\Delta (G)$, they constructed a 2-degenerate graph $G$ such that $\omega (G^2)=\frac{5}{2}\Delta (G)$. Note that if $G$ is a 2-degenerate graph, then $mad(G)<4$. Thus, we have that \[ {\displaystyle \frac{5}{2} Δ(G) \leq \max \{χ(G^2) : G \mbox{ is a 2-degenerate graph} \} \leq 3 Δ(G) +1}. \] So, it was naturally asked whether there exists a constant $D_0$ such that $\chi (G^2)\le \frac{5}{2}\Delta (G)$ if $G$ is a 2-degenerate graph with $\Delta (G)\ge D_0$. Recently Cranston and Yu [3] showed that $\omega (G^2)\le \frac{5}{2}\Delta (G)+72$ if $G$ is a 2-degenerate graph, and $\omega (G^2)\le \frac{5}{2}\Delta (G)+60$ if $G$ is a 2-degenerate graph with $\Delta (G)\ge 1729$. We show that there exists a constant $D_0$ such that $\omega (G^2)\le \frac{5}{2}\Delta (G)$ if $G$ is a 2-degenerate graph with $\Delta (G)\ge D_0$. This upper bound on $\omega (G^2)$ is tight by the construction in [6].

32 pages