Tight Upper Bound on the Clique Size in the Square of 2‐Degenerate Graphs

ABSTRACT The square of a graph , denoted , has the same vertex set as and has an edge between two vertices if the distance between them in is at most 2. In general, for every graph . Charpentier (2014) asked whether if . But Hocquard, Kim, and Pierron (2019) answered his question negatively. For every even value of g, they constructed a 2‐degenerate graph such that . Note that if is a 2‐degenerate graph, then . Thus, we have that So, it was naturally asked whether there exists a constant such that if is a 2‐degenerate graph with . Recently, Cranston and Yu (2024) showed that if is a 2‐degenerate graph, and if is a 2‐degenerate graph with . We show that there exists a constant such that if is a 2‐degenerate graph with . This upper bound on is tight by the construction in Hocquard, Kim, and Pierron.