0.25pt 20

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

Daniel W. Cranston Department of Computer Science, Virginia Commonwealth
University, Richmond, VA, USA<EMAIL_ADDRESS>Gexin Yu Department of
Mathematics, William & Mary, Williamsburg, VA, USA<EMAIL_ADDRESS>
###### Abstract

Hocquard, Kim, and Pierron constructed, for every even integer $D\geqslant 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 $\textrm{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})\leqslant\frac{5}{2}D+72$ (with
$\omega(G^{2})\leqslant\frac{5}{2}D+60$ when $D$ is sufficiently large). And
if $G$ has $\textrm{mad}(G)<4$ and maximum degree $D$, then
$\omega(G^{2})\leqslant\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.

##  1 Introduction

The _square, $G^{2}$_††margin:  square, $G^{2}$ , of a graph $G$ is formed
from $G$ by adding an edge between each pair of vertices at distance 2 in $G$.
A graph $G$ is _$k$ -degenerate_ if each subgraph of $G$ has a vertex of
degree at most $k$. (Equivalently, we require that $G$ has a vertex order
$\sigma$ such that each vertex has at most $k$ neighbors later in $\sigma$.)
And the _maximum average degree_ of $G$, denoted _$\textrm{mad}(G)$_ ††margin:
$\textrm{mad}(G)$ is defined as $\textrm{mad}(G):=\max_{H\subseteq
G}2|E(H)|/|V(H)|$. In this paper we study the maximum size of a clique in
$G^{2}$, denoted $\omega(G^{2})$, over all 2-degenerate graphs $G$ and, more
generally, over all graphs $G$ with $\textrm{mad}(G)<4$. Hocquard, Kim, and
Pierron [11] constructed 2-degenerate graphs $G_{D}$ with maximum degree $D$
such that $\omega(G_{D}^{2})=5D/2$, for every positive even integer $D$. This
construction gives a lower bound on the maximums that we seek. Our two main
results prove that this lower bound is sharp, up to small additive constants.

######  Theorem 1.

Fix a positive integer $D$. If a graph $G$ is 2-degenerate with
$\Delta(G)\leqslant D$, then $\omega(G^{2})\leqslant\frac{5}{2}D+72$.
Furthermore, if $D\geqslant 1729$, then
$\omega(G^{2})\leqslant\frac{5}{2}D+60$.111The remark just before Section 2
details subsequent improvement of this result to a version that is sharp [14].

######  Theorem 2.

Fix a positive integer $D$. If a graph $G$ has $\textrm{mad}(G)<4$ and
$\Delta(G)\leqslant D$, then $\omega(G^{2})\leqslant\frac{5}{2}D+532$.

Over the past 40 years tremendous effort has gone into proving upper bounds on
the chromatic number of squares of graphs; for a recent survey, see [5]. If a
graph $G$ has maximum degree $\Delta$, then trivially
$\chi(G^{2})\geqslant\Delta+1$ since, for every vertex $v$, the closed
neighborhood $N[v]$ is a clique in $G^{2}$. By greedily coloring vertices in
the reverse of order $\sigma$ above, we get $\chi(G)\leqslant k+1$. It is easy
to check that $G^{2}$ is $\Delta^{2}$-degenerate; thus
$\chi(G^{2})\leqslant\Delta^{2}+1$. This bound holds with equality for the
5-cycle and the Petersen graph (but only for 1 or 2 other connected graphs).

In general, the upper bound $\chi(G^{2})\leqslant\Delta^{2}$ cannot be
improved much, as witnessed by incidence graphs of finite projective planes.
To prove better upper bounds on $\chi(G^{2})$, researchers have focused on
more structured classes of graphs. For brevity, we mention only two types of
these.

Erdős and Nešetřil introduced the notion of strong edge-coloring, which is
equivalent to coloring the square of the line graph $L(G)$. They conjectured
that if $G$ has $\Delta\leqslant D$, then its strong edge-chromatic number,
denoted $\chi^{\prime}_{s}(G)$, is at most $\frac{5}{4}D^{2}$; when $D$ is
even this is achieved by a graph $G$ with $|E(G)|=\frac{5}{4}D^{2}$. So they
conjectured that the worst case is when $L(G)^{2}$ is complete. The current
strongest bound [12] is $\chi^{\prime}_{s}(G)\leqslant 1.772D^{2}$. This bound
is far from the conjecture, which has motivated interest in bounding the
clique number of the square of the line graph $\omega(L(G)^{2})$. Initial
efforts in this vein [4] showed that if $L(G)^{2}$ is a complete graph, then
its order is at most $\frac{5}{4}D^{2}$. Later, Śleszyńska-Nowak [15] showed
that $\omega(L(G)^{2})\leqslant\frac{3}{2}D^{2}$. More recently, Faron and
Postle [7] strengthened this bound to
$\omega(L(G)^{2})\leqslant\frac{4}{3}D^{2}$.

The other class of graphs that we discuss in detail is planar graphs. In 1977,
Wegner conjectured that if $G$ is planar with $\Delta\geqslant 8$, then
$\chi(G^{2})\leqslant\lfloor\frac{3}{2}\Delta\rfloor+1$. (His conjecture is a
chief reason for much of the interest in bounding $\chi(G^{2})$.) To see that
this conjecture is sharp, consider a so-called “fat triangle” formed from
$K_{3}$ by replacing each edge with $s$ parallel edges. Subdivide once all
edges of the fat triangle except for two non-parallel edges. The resulting
graph $G$ has $\Delta=2s$ and $G^{2}$ is a complete graph of order $3s+1$.
(For smaller $\Delta$, Wegner conjectured weaker upper bounds on
$\chi(G^{2})$. In each case, the conjectured upper bound is sharp, as
witnessed by a graph whose square is complete.) Wegner’s Conjecture has been
proved asymptotically [10]: $\chi(G^{2})\leqslant\frac{3}{2}\Delta(1+o(1))$,
where the $o(1)$ is as $\Delta\to\infty$. But for exact bounds, the problem
remains wide open except for the case $\Delta=3$ (where 7 colors are both
sufficient and often necessary), which was confirmed by two groups [9, 16].
This state of affairs motivates interest in bounds on $\omega(G^{2})$. Amini
et al. [1] proved that $\omega(G^{2})\leqslant\frac{3}{2}\Delta+O(1)$ for
graphs embedded in each fixed surface. For the plane, they proved
$\omega(G^{2})\leqslant\frac{3}{2}\Delta+76$ when $\Delta\geqslant 11616$.
Finally, the first author proved the best possible result
$\omega(G^{2})\leqslant\frac{3}{2}\Delta+1$, when $\Delta\geqslant 36$.222The
paper [1] attributes to Cohen and van den Heuvel the bound
$\omega(G^{2})\leqslant\lfloor\frac{3}{2}\Delta\rfloor+1$ for all planar
graphs with $\Delta\geqslant 41$. However, we contacted Cohen and van den
Heuvel, who informed us that they have neither written a proof of this
statement, nor have plans to do so. Thus, the problem remained open until [6].

Now we reach the specific paper that inspired our present work. Hocquard, Kim,
and Pierron [11] studied $\chi(G^{2})$ when $\textrm{mad}(G)<4$. They showed
that $G^{2}$ is $3\Delta$-degenerate; thus, $\chi(G^{2})\leqslant 3\Delta+1$.
They also constructed such a graph $G$ with $\omega(G^{2})=\frac{5}{2}\Delta$,
whenever $\Delta$ is even; see Example 1. As a possible strengthening, they
asked the two questions below.

  1. (i)

Is there $D_{0}$ such that every 2-degenerate graph $G$ with
$\Delta(G)\geqslant D_{0}$ has $\chi(G^{2})\leqslant\frac{5}{2}\Delta(G)$?

  2. (ii)

Is there $D_{0}$ such that every $G$ with $\Delta(G)\geqslant D_{0}$ and
$\textrm{mad}(G)<4$ has $\chi(G^{2})\leqslant\frac{5}{2}\Delta(G)$?

A natural approach to these questions is to try to strengthen the bound on the
degeneracy of $G^{2}$ whenever $G$ is 2-degenerate. However, this is not
really possible. In Example 2 below, for each integer $D\geqslant 2$, we
construct a family of graphs $G$ such that $G$ is 2-degenerate, $\Delta(G)=D$,
and $G^{2}$ is _not_ $(3D-5)$-degenerate.

Figure 1: A graph $G_{D}$ with maximum degree $D$. In $G_{D}^{2}$, the black
vertices form a clique of order $5D/2$. Each pair of black vertices with no
common white neighbor has a gray neighbor that is adjacent only to them
(though only a few such gray vertices are shown).

######  Example 1 ([11]).

For every positive even integer $D$, there exists a 2-degenerate graph $G_{D}$
with maximum degree $D$ such that $\omega(G_{D}^{2})=\frac{5}{2}D$; see Figure
1.

Fix a positive integer $D$ that is divisible by 4. To form $G_{D}$, (1) start
with the complete graph $K_{5}$. (2) Replace each edge $vw$ with a copy of
$K_{2,D/4}$, identifying the vertices in the part of size 2 with $v$ and $w$.
(3) Now for each pair, $x$ and $y$, of vertices of degree 2 with no common
neighbor, add a vertex $z_{xy}$ adjacent to both $x$ and $y$. Call the
resulting graph $G_{D}$. Clearly, $G_{D}$ is 2-degenerate. It is easy to check
that also $\omega(G_{D}^{2})=\frac{5}{2}D$; the set $S$ of all vertices
adjacent to two vertices of the original $K_{5}$ is a clique in $G_{D}^{2}$.
Furthermore, $G_{D}$ has maximum degree $4(D/4)=D$; this is the degree of each
vertex of the original $K_{5}$ and every other vertex has lower degree. (If
$D$ is even, but not divisible by 4, perform the construction above with
$D^{\prime}:=D+2$, but for each edge on the outer 5-cycle of the original
$K_{5}$, after (2) but before (3), delete one vertex in the part of size
$D^{\prime}/4$.) $\diamondsuit$

######  Example 2.

For each positive integer $D$, there exists a graph $H_{D}$ that is
2-degenerate and has maximum degree $D$, but such that $H_{D}^{2}$ is not
$(3D-5)$-degenerate; see Figure 2.

Let $G_{D}$ be a $D$-regular graph with $4s$ vertices, for some $s\geqslant 3$
(for example, $G_{D}$ could be a circulant); let $T:=V(G_{D})$. Subdivide each
edge of $G_{D}$; call the resulting graph $G_{D}^{\prime}$ and call these new
vertices $S$. Build an auxiliary graph $J$ with vertex set $S$ and $vw\in
E(J)$ if $v$ and $w$ are distinct and have no common neighbor in
$G_{D}^{\prime}$. Note that $J$ is regular of degree
$|E(G_{D})|-(2D-1)=2sD-(2D-1)>\frac{1}{2}|E(G_{D})|=\frac{1}{2}|S|=\frac{1}{2}|V(J)|$.
Thus, by Dirac’s Theorem, $J$ has a Hamiltonian cycle, $C$. By deleting the
edges of $C$ and repeating the argument, we find
$\lceil\frac{1}{2}(D-2)\rceil$ edge-disjoint Hamiltonian cycles $C_{i}$ in
$J$. If $D$ is even, let $J_{1}$ be the union of these cycles $C_{i}$; if $D$
is odd, let $J_{1}$ be the union of all but one of these cycles $C_{i}$ and a
1-factor from the final cycle. Note that $J_{1}$ is $(D-2)$-regular. Now, for
each edge $vw\in E(J_{1})$, add to $G^{\prime}_{D}$ a new vertex $z_{vw}$
adjacent to $v$ and $w$; call the resulting graph $H_{D}$. Now we can check
that $H_{D}$ is 2-degenerate with maximum degree $D$ and $H_{D}^{2}[S]$ is
regular of degree $3D-4$. $\diamondsuit$

$G_{D}$$G_{D}^{\prime}$$G_{D}^{\prime}$$G_{D}^{\prime}$$G_{D}^{\prime}$$C_{1}$,
$C_{2}$$\in J$$J_{1}$$H_{D}$$H_{D}$$H_{D}$$H_{D}$ Figure 2: The process of
forming $H_{D}$ from $G_{D}$ in Example 2, when $D=5$, as viewed from the
perspective of a single edge in $G_{D}$.

Example 2 shows that even proving the bound $\chi(G^{2})\leqslant 3D-4$ will
require new ideas. The degeneracy of $G^{2}$ alone will not suffice. (We can
generalize Example 2 to something similar for $k$-degenerate graphs with
arbitrary $k\geqslant 2$. But to keep our focus here on 2-degenerate graphs,
we defer these details to Example 3.)

###  1.1 Overview of Proofs

The proofs of both Theorems 1 and 2 follow a similar outline, though the
latter is more complicated. We have made some effort to minimize the constant
in Theorem 1, but have not made much effort in this direction in Theorem 2,
prefering to present a simpler proof.

######  Definition 1.

A _$k$ -degeneracy order_††margin:  $k$-degeneracy order for a graph $G$ is an
order of $V(G)$ such that each vertex has at most $k$ neighbors later in the
order. A graph $G$ is _nice_ ††margin:  nice , w.r.t. a clique $S$ in $G^{2}$,
if (a) $S$ is a clique in $G^{2}$, (b) $S$ is an independent set in $G$, and
(c) $G$ has a $2$-degeneracy order $\sigma$ such that all vertices of $S$
appear consecutively in $\sigma$. The notion is inspired by the construction
of Hocquard, Kim, and Pierron, described in Example 1, which is indeed nice.

In Section 2, we consider only graphs $G$ that are nice w.r.t. a maximum
clique $S$ in $G^{2}$.

######  Theorem 3.

If $G$ is nice w.r.t. a maximum clique $S$ in $G^{2}$ and $\Delta(G)\leqslant
D$, then $\omega(G^{2})\leqslant\frac{5}{2}D$.

Theorem 3 is exactly sharp, as witnessed by the graphs in Example 1. (In fact,
these graphs and a class of similar ones are the unique extremal examples, as
can be seen by studying the proof more carefully. We give more details
following the proof of Proposition 1.) To prove Theorem 1, we consider a graph
$G$ that is 2-degenerate and fix a vertex subset $S$ such that $S$ is a
maximum clique in $G^{2}$. We show that there exists $S^{\prime}\subseteq S$
such that $|S\setminus S^{\prime}|\leqslant 72$ and there exists a graph
$G^{\prime}$ (a subgraph of $G$) such that $G^{\prime}$ is nice w.r.t.
$S^{\prime}$. Then the result follows by applying Theorem 3 to $G^{\prime}$.
To prove Theorem 2, our approach is similar. We consider a graph $G$ with
$\textrm{mad}(G)<4$ and fix a vertex subset $S$ such that $S$ is a maximum
clique in $G^{2}$. We show that there exists $S^{\prime}\subseteq S$ such that
$|S\setminus S^{\prime}|\leqslant 460$ and there exists a graph $G^{\prime}$
(a subgraph of $G$) such that $G^{\prime}$ is nice w.r.t. $S^{\prime}$. Then
the result again follows by applying Theorem 3 to $G^{\prime}$.

In the proof of Theorem 1 (resp. Theorem 2), we introduce a technique of
“token passing”, where vertices are deleted in a 2-degeneracy (resp.
3-degeneracy) order $\sigma$ and each vertex passes tokens, immediately before
it is deleted, to its neighbors later in $\sigma$. These tokens facilitate a
sort of amortized analysis that is common in certain areas of algorithm
analysis. However, we have not previously seen it used for the types of
problems we consider in the present paper. And we believe it is likely to be
applicable to further similar problems.

######  Remark.

After the preparation of this manuscript, Kim and Lian [14] extended our ideas
to strengthen Theorem 1. Specifically, they showed that if $G$ is 2-degenerate
and has maximum degree $D$ at least $3.3\times 10^{6}$, then
$\omega(G^{2})\leqslant\frac{5}{2}D$. This upper bound on $\omega(G^{2})$ is
best possible.

##  2 Big Cliques in Squares of Nice 2-Degenerate Graphs

The goal of this section is to prove the following result.

######  Theorem 4.

Let $H$ be a multigraph with $\Delta(H)\leqslant D$, for some positive integer
$D$. If each edge of $H$ shares at least one endpoint with all but at most
$D-2$ other edges of $H$, then $|E(H)|\leqslant\frac{5}{2}D$.

Intuitively, Theorem 4 essentially rephrases Theorem 3 in terms of edges in
multigraphs, for which we have standard terminology. More formally, we have
the following proposition.

######  Proposition 1.

Theorem 4 implies Theorem 3.

###### Proof.

Let $G$††margin:  $G$, $S$ be nice w.r.t. a maximum clique $S$ in $G^{2}$ and
$\Delta(G)\leqslant D$. We may assume that $V(G)\setminus S$ is an independent
set; otherwise we delete all edges induced by $V(G)\setminus S$ and again call
the resulting graph $G$ (note that it still satisfies all hypotheses of
Theorem 3). Let _$\sigma$_ ††margin:  $\sigma$ be a 2-degeneracy order
witnessing that $G$ is nice w.r.t. $S$ and partition $V(G)$ into _$R,S,T$_
††margin:  $R,S,T$ , where $R$ are vertices before $S$ in $\sigma$, and $T$
are vertices after $S$. Form _$H$_ ††margin:  $H$ from $G$ as follows: delete
all vertices of $R$ and contract one edge incident to each vertex of $S$.
Figure 3 shows an example.

$\rightarrow$ Figure 3: The graph $G_{D}$ (left) from Example 1 and the graph
$H_{D}$ (right) produced from $G_{D}$ by the operations described in the first
paragraph proving Proposition 1.

It is easy to check that $\Delta(H)\leqslant\Delta(G)$ and $|E(H)|=|S|$.
Consider $v\in S$. Since $\sigma$ is a 2-degeneracy order, each neighbor $w\in
R$ of $v$ gives rise to at most one edge $vv^{\prime}\in E(G^{2})$. If $v$ has
at most one neighbor in $T$, then $v$ has degree at most $2(D-1)$ in $G^{2}$,
so $|S|\leqslant 2D$. So assume instead that $v$ has at least two neighbors in
$T$ (exactly two, in fact, since $\sigma$ is a 2-degeneracy order). Since
$\Delta(G)\leqslant D$, vertex $v$ has at most $D-2$ neighbors in $R$. So for
all but at most $D-2$ vertices $v^{\prime}$ in $S$, vertex $v$ has a neighbor
$w$ in $T$ in common with $v^{\prime}$. Thus, the edge in $H$ arising from $v$
has a common endpoint with all edges of $H$ except for at most $D-2$. Hence,
$H$ satisfies the hypotheses of Theorem 4. As a result,
$\omega(G^{2})=|E(H)|\leqslant\frac{5}{2}D$, as desired. ∎

To see that Theorem 4 is best possible, start with $K_{5}$ and replace each
edge with $D/4$ parallel edges. We can also say a bit about uniqueness and
stability. The bulk of the work in proving Theorem 4 is considering the case
$|V(H)|\geqslant 6$ and proving that $|E(H)|\leqslant\frac{5}{2}D$; in fact,
we can prove that this inequality is strict. Thus, every graph $H$ that
satisfies Theorem 4 with equality has $|V(H)|=5$. However, we do not have much
“stability”, since (for infinitely many values of $D$) there is a graph $H$
with $|V(H)|=6$ and $|E(H)|=\frac{5}{2}D-5$. Namely, start with $K_{6}$ and
replace each edge with $\frac{1}{6}(D-2)$ parallel edges. In fact, even the
extremal examples on 5 vertices are not unique. Such examples require only
that the graph is $D$-regular and that each edge shares an endpoint with all
but at most $D-2$ other edges. For large values of $D$, there are many such
graphs. For example, starting with the example in the first sentence of this
paragraph, we can pick an arbitrary 5-cycle $\mathcal{C}$ and delete $2$
copies of each edge on $\mathcal{C}$. This gives an example with maximum
degree $D-4$ that differs from that first example.

###  2.1 Proof of Theorem 4

We assume Theorem 4 is false and let $H$ be a counterexample minimizing
$|E(H)|+|V(H)|$.

######  Definition 2.

For a multigraph $H$, we write $H_{0}$††margin:  $H_{0}$, $\overline{H_{0}}$
for the underlying simple graph and $\overline{H_{0}}$ for the complement of
this simple graph. For each $vw\in E(H)$, we write _$\mu(vw)$_ ††margin:
$\mu(vw)$ to denote the multiplicity of edge $vw$. For each $v\in V(H)$, let
_$E(v)$_ ††margin:  $E(v)$ denote the set of edges incident to $v$.

If we can show that $H_{0}$ is a complete graph, say $K_{h}$, then we can
conclude with a simple counting argument, taking advantage of the symmetry of
$K_{h}$; see Claim 2.9. So this is the main work of the present section.
Equivalently, we show that $\overline{H_{0}}$ is edgeless. To this end, we
show that $\overline{H_{0}}$ is, first, a vertex disjoint union of stars
(Claim 2.6); second, a matching (Claim 2.7); and third, a graph with at most
one edge (Claim 2.8).

######  Claim 2.1.

$H$ is connected and $|V(H)|\geqslant 6$.

Proof. Since $|E(H)|+|V(H)|$ is minimum, $H$ has no isolated vertices. If $H$
is disconnected, then some edge $e$ of $H$ is in a component with at most half
of the edges of $H$. But now $e$ has no endpoint in common with at least
$\frac{1}{2}|E(H)|>\frac{5}{4}D$, a contradiction. If $|V(H)|\leqslant 5$,
then $|E(H)|=\frac{1}{2}\sum_{v\in V(H)}d(v)\leqslant\frac{5}{2}D$, so $H$ is
not a counterexample.  $\diamondsuit$

######  Claim 2.2.

If $vw\in E(H)$, then $d(v)+d(w)-\mu(vw)\geqslant\frac{3}{2}D+2$.

Proof. By definition, $D-2\geqslant|E(H)\setminus(E(v)\cup
E(w))|=|E(H)|-(d(v)+d(w)-\mu(vw))$. Thus,
$d(v)+d(w)-\mu(vw)\geqslant|E(H)|-(D-2)\geqslant\frac{3}{2}D+2$.
$\diamondsuit$

######  Claim 2.3.

We have $\delta(H_{0})\geqslant 3$.

Proof. By Claim 2.1, $d_{H_{0}}(v)\geqslant 1$ for each $v\in V(H_{0})$.
Suppose there exists $v\in V(H_{0})$ with $d_{H_{0}}(v)=1$; denote its
neighbor by $w$. Claim 2.2 gives
$\frac{3}{2}D<d(w)+(d(v)-\mu(vw))=d(w)\leqslant D$, a contradiction. So
suppose instead that $d_{H_{0}}(v)=2$; denote the neighbors of $v$ by $w$ and
$x$. By symmetry, assume that $\mu(vw)\leqslant\mu(vx)$, so
$\mu(vw)\leqslant\frac{1}{2}D$. Similar to above,
$\frac{3}{2}D<d(v)+d(x)-\mu(vx)=d(x)+\mu(vw)\leqslant\frac{3}{2}D$, a
contradiction. Thus, $\delta(H_{0})\geqslant 3$, as claimed.  $\diamondsuit$

######  Claim 2.4.

If $v,w,x,y\in V(H)$ are distinct vertices and $vw,xy\in E(H)$, then
$\mu(vx)+\mu(vy)+\mu(wx)+\mu(wy)\geqslant\frac{1}{2}D+2$.

Proof. If an edge $e$ shares an endpoint with both $vw$ and $xy$, then $e$ is
counted by $\mu(vx)+\mu(vy)+\mu(wx)+\mu(wy)$. Each of $vw$ and $xy$ shares an
endpoint with all but at most $D-2$ edges of $H$, so
$\mu(vx)+\mu(vy)+\mu(wx)+\mu(wy)\geqslant|E(H)|-|\\{vw,xy\\}|-2(D-2)\geqslant\frac{5}{2}D-(2D-2)=\frac{1}{2}D+2$.
$\diamondsuit$

######  Claim 2.5.

For all distinct $v,w\in V(H)$, we have $\sum_{x\in
V\setminus\\{v,w\\}}\mu(vx)>\frac{1}{2}D$; so $\mu(vw)<\frac{1}{2}D$.

Proof. First suppose that $vw\in E(H)$. By Claim 2.2, we have
$\frac{3}{2}D<d(w)+d(v)-\mu(vw)=d(w)+(\sum_{x\in
V\setminus\\{v\\}}\mu(vx))-\mu(vw)=d(w)+\sum_{x\in
V\setminus\\{v,w\\}}\mu(vx)\leqslant D+\sum_{x\in
V\setminus\\{v,w\\}}\mu(vx)$. Thus, $\frac{1}{2}D<\sum_{x\in
V\setminus\\{v,w\\}}\mu(vx)$, as claimed. So $\mu(vw)<D-\frac{1}{2}D$. Suppose
instead that $vw\notin E(H)$. By Claim 2.1, $v$ has some incident edge $vz$.
As above, $\sum_{x\in V\setminus\\{v,z\\}}\mu(vx)>\frac{1}{2}D$. Now
$\mu(vw)=0$, so $\sum_{x\in V\setminus\\{v,w\\}}\mu(vx)>\sum_{x\in
V\setminus\\{v,w,z\\}}\mu(vx)=\sum_{x\in
V\setminus\\{v,z\\}}\mu(vx)>\frac{1}{2}D$, as claimed.  $\diamondsuit$

######  Claim 2.6.

The graph $\overline{H_{0}}$ is a vertex disjoint union of stars.

Proof. First suppose, to the contrary, that $\overline{H_{0}}$ contains a
triangle $vwx$; see Figure 4(a). That is, $vw,vx,wx\notin E(H_{0})$. Since
$\delta(H_{0})\geqslant 3$, there exist $y$ such that $vy\in E(H_{0})$. By
Claim 2.5, we have $\sum_{z\in V\setminus\\{w,y\\}}\mu(wz)>\frac{1}{2}D$ and
$\sum_{z\in V\setminus\\{x,y\\}}\mu(xz)>\frac{1}{2}D$. Since $\mu(wx)=0$, the
sets of edges counted by these two inequalities are disjoint. Thus, there
exist more than $D$ edges that share no endpoint with edge $vy$. This
contradicts our definition of $H$ (in the hypothesis of the theorem). Thus,
$\overline{H_{0}}$ is triangle-free.

Now suppose instead that $\overline{H_{0}}$ contains edges $vw,wx,xy$; see
Figure 4(b). By the previous paragraph, $vx,wy\notin E(\overline{H_{0}})$. Now
Claims 2.4 and 2.5 give
$\frac{1}{2}D+2\leqslant\mu(vw)+\mu(wx)+\mu(xy)+\mu(vy)=\mu(vy)<\frac{1}{2}D$,
a contradiction. This finishes the proof of the claim.  $\diamondsuit$

$v$$w$$x$$y$(a)$v$$w$$x$$y$(b) Figure 4: The proof of Claim 2.6: (a) a
triangle $vwx$ in $\overline{H_{0}}$, and (b) a $P_{4}$ $vwxy$ in
$\overline{H_{0}}$.

######  Claim 2.7.

The graph $\overline{H_{0}}$ is a matching.

Proof. Suppose, to the contrary, that there exist distinct $v,w,x\in V(H_{0})$
with $vw,vx\in E(\overline{H_{0}})$; that is, $vw,vx\notin E(H_{0})$. Since
$\delta(H_{0})\geqslant 3$, there exists $y$ such that $vy\in E(H_{0})$. By
Claim 2.6, we know $wx,wy,xy\in E(H_{0})$; see Figure 5(a). Thus, Claim 2.4
gives $\mu(vw)+\mu(vx)+\mu(yw)+\mu(yx)>\frac{1}{2}D$. However,
$\mu(vw)=\mu(vx)=0$, so $\mu(yw)+\mu(yx)>\frac{1}{2}D$. Since,
$\delta(H_{0})\geqslant 3$, there exist $y^{\prime},z$ such that
$y,y^{\prime},z$ are distinct neighbors of $v$ in $H_{0}$. Repeating the
arguments above for $y^{\prime}$, we get that
$\mu(y^{\prime}w)+\mu(y^{\prime}x)>\frac{1}{2}D$. But now $vz$ has more than
$D$ edges with which it shares no endpoint (those counted by
$\mu(yw)+\mu(yx)+\mu(y^{\prime}w)+\mu(y^{\prime}x)$), a contradiction.
$\diamondsuit$

$v$$w$$x$$y$$y^{\prime}$$z$(a)$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$(b)
Figure 5: The proofs of (a) Claim 2.7 and (b) Claim 2.8.

######  Claim 2.8.

The graph $\overline{H_{0}}$ contains at most one edge.

Proof. First suppose instead that $\overline{H_{0}}$ has at least 3 edges;
that is, by Claim 2.7, there are $v_{1}v_{2},v_{3}v_{4},v_{5}v_{6}\notin
E(H_{0})$. See Figure 5(b). By Claim 2.7, we know $v_{1}v_{3},v_{2}v_{4}\in
E(H_{0})$. So Claim 2.4 implies that
$\mu(v_{2}v_{3})+\mu(v_{1}v_{4})>\frac{1}{2}D$. Similarly,
$\mu(v_{1}v_{3})+\mu(v_{2}v_{4})>\frac{1}{2}D$. We can now repeat both of
these arguments twice, first with $v_{5}v_{6}$ in place of $v_{3}v_{4}$, and
second with $v_{5}v_{6}$ in place of $v_{1}v_{2}$. Thus, we have partitioned
the 12 edges induced (in $H_{0}$) by $v_{1},\ldots,v_{6}$ into 6 pairs, each
of which has sum of multiplicities greater than $\frac{1}{2}D$. Thus,
$|E(H)|>6(\frac{1}{2}D)=3D$. However, applying the hypothesis of the theorem
to edge $v_{1}v_{3}$ gives $|E(H)|\leqslant d(v_{1})+d(v_{3})+(D-2)<3D$, a
contradiction.

Now suppose instead that $\overline{H_{0}}$ has only two edges. That is,
$v_{1}v_{2},v_{3}v_{4}\notin E(H_{0})$. As above, we conclude that
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ induces (in $H$) more than $D$ edges. Now
there exists $v_{5}v_{6}\in E(H_{0})$ (with
$v_{5},v_{6}\notin\\{v_{1},v_{2},v_{3},v_{4}\\}$; recall that $|V(H)|\geqslant
6$, by Claim 2.1). But now there exist more than $D$ edges with which
$v_{5}v_{6}$ shares no endpoint, a contradiction.  $\diamondsuit$

######  Claim 2.9.

The graph $\overline{H_{0}}$ contains exactly one edge. Further,
$|V(H_{0})|=6$.

Proof. Suppose to the contrary, by Claim 2.8, that $\overline{H_{0}}$ contains
no edges; that is $H_{0}$ is a complete graph. Let _$h$_ ††margin:  $h$
$:=|V(H_{0})|$. By assumption, every edge $vw\in E(H)$ shares an endpoint with
all but at most $D-2$ edges. Thus, for every pair $v,w\in V(H)$, we have
$d_{H}(v)+d_{H}(w)-\mu(vw)\geqslant|E(H)|-(D-2)$. Summing over all
$\binom{h}{2}$ edges of $H_{0}$ gives

$\sum_{vw\in
E(H_{0})}\left(d_{H}(v)+d_{H}(w)-\mu(vw)\right)\geqslant\sum_{vw\in
E(H_{0})}\left(|E(H)|-(D-2)\right)$

Each edge of $H$ is counted on the left exactly $2h-3$ times. Thus, we get
$(2h-3)|E(H)|\geqslant\binom{h}{2}|E(H)|-\binom{h}{2}(D-2)$. This simplifies
to
$|E(H)|\leqslant(D-2)\frac{h(h-1)}{(h-2)(h-3)}=(D-2)(1+\frac{4h-6}{(h-2)(h-3)})=(D-2)(1+\frac{6}{h-3}+\frac{-2}{h-2})$.
This expression is decreasing with $h$, so is maximized when $h=6$, where we
get $|E(H)|\leqslant(D-2)(1+\frac{6}{3}+\frac{-2}{4})=(D-2)\frac{5}{2}$. Thus,
$\overline{H_{0}}$ contains exactly one edge, as claimed.

Let $vw$ be the unique edge in $\overline{H_{0}}$. Now we repeat the argument
above. The main difference is that the sum on the right now has only
$\binom{h}{2}-1$ terms. There are also some edges that are counted only $2h-4$
times, but we can still upper bound the left side by $(2h-3)|E(H)|$. That is
$(2h-3)|E(H)|\geqslant(\binom{h}{2}-1)|E(H)|-(\binom{h}{2}-1)(D-2)$. This
simplifies to
$|E(H)|\leqslant(D-2)\frac{h^{2}-h-2}{(h-1)(h-4)}=(D-2)(1+\frac{4h-6}{(h-1)(h-4)})=(D-2)(1+\frac{2/3}{h-1}+\frac{10/3}{h-4})$.
Again this expression is decreasing with $h$. When $h=6$, we get
$|E(H)|\leqslant\frac{14}{5}(D-2)$, so we cannot rule out that case. But when
$h=7$, we get $|E(H)|\leqslant\frac{20}{9}(D-2)$. Thus $h=6$, as claimed.
$\diamondsuit$

$x$$y$$H_{0}$$x$$y$$H_{1}$ Figure 6: The graphs $H_{0}$ and $H_{1}$ in the
proof of Claim 2.10.

######  Claim 2.10.

The graph $H$ does not exist; that is, Theorem 4 is true.

Proof. Suppose the claim is false. By Claim 2.9, we must have $H_{0}=K_{6}-e$.
Denote by $x,y$ the nonadjacent pair in $H_{0}$; see Figure 6. We define a
multigraph $H_{1}$ that has $H_{0}$ as its underlying simple graph, has
$\mu(e)=2$ for each edge $e$ of $H_{0}$ incident to $x$ or $y$, and $\mu(e)=1$
for each other edge $e$ of $H_{0}$. Similar to above, for each edge $vw\in
E(H_{0})$ we have $d_{H}(v)+d_{H}(w)-\mu(vw)\geqslant|E(H)|-(D-2)$. Summing
over all $14+8=22$ edges of $H_{1}$ gives333In other words, $H_{1}$ is simply
a convenient way to encode the multiplicities with which we want to sum the 14
inequalities $d_{H}(v)+d_{H}(w)-\mu(vw)\geqslant|E(H)|-(D-2)$ arising from the
14 edges $vw$ of $H_{0}$.

$\sum_{vw\in
E(H_{1})}\left(d_{H}(v)+d_{H}(w)-\mu(vw)\right)\geqslant\sum_{vw\in
E(H_{1})}\left(|E(H)|-(D-2)\right)$

It is straightforward to check that each edge of $H$ is counted exactly 13
times. Thus, the inequality above can be rewritten as $13|E(H)|\geqslant
22|E(H)|-22(D-2)$, which simplifies to $|E(H)|\leqslant\frac{22}{9}(D-2)$.
This contradiction proves the claim, which in turn proves the theorem.
$\diamondsuit$

##  3 Big Cliques in Squares of 2-Degenerate Graphs

Fix a positive integer $D$. Let _$f(D)$_ ††margin:  $f(D)$ be the maximum size
of a clique $S$ in the square of a 2-degenerate graph $G$ with
$\Delta(G)\leqslant D$. It is easy to verify that if $G$ is $k$-degenerate
with $\Delta(G)\leqslant D$, then $G^{2}$ has degeneracy at most
$k(D-1)+(D-k)(k-1)$; this is witnessed by any vertex order showing that $G$ is
$k$-degenerate. So, when $k=2$, $G^{2}$ is $(3D-4)$-degenerate. Thus,
$f(D)\leqslant 3D-3$. Example 1 shows that $f(D)\geqslant\frac{5}{2}D$, when
$D$ is even. In fact, the graph $G$ in Example 1 has a maximum clique $S$ in
$G^{2}$ the vertices of which form an independent set in $G$. Furthermore,
there exists a 2-degeneracy order $\sigma$ for $G$ in which the vertices of
$S$ appear consecutively. The goal of this section is to show that if
$f(D)>\frac{5}{2}D$, then this is witnessed by a graph $G$ where $S$ behaves
“nearly” as it does above. More specifically, we show the following (recall
the meaning of “nice” from Definition 1).

######  Theorem 5.

There exists a constant $c$ such that for every positive integer $D$ some
2-degenerate graph $G$ with $\Delta(G)\leqslant D$ is nice w.r.t. a clique $S$
in $G^{2}$ and $|S|\geqslant f(D)-c$. In fact, $c=72$ suffices and, when $D$
is sufficiently large, $c=60$ suffices.

###### Proof.

We prove the theorem with $c=72$, but we have not made significant effort to
minimize $c$. (A small trick at the end improves this to $c=60$ when
$D\geqslant 1729$.)

Fix a positive integer $D$††margin:  $D$, $G$, $S$ , and let $G$ be a
2-degenerate graph with maximum degree at most $D$ such that $G^{2}$ has a
clique $S$ of order $f(D)$. Subject to this, choose $G$ to minimize
$|V(G)|+|E(G)|$. We assume that $f(D)\geqslant\frac{5}{2}D+60$; otherwise, we
are done by Example 1. Note that every vertex $v\in V(G)$ must have a neighbor
in $S$; otherwise, deleting $v$ contradicts the minimality of $G$.

Let _$\sigma$_ ††margin:  $\sigma$ be a vertex order witnessing that $G$ is
2-degenerate. Subject to this, choose $\sigma$ so the first vertex in $S$
appears as late as possible in $\sigma$. We delete the vertices of $G$ in the
order $\sigma$. Each time we delete a vertex $v$ of $S$, vertex $v$ gives a
“primary” token to each of its neighbors later in $\sigma$. Moreover, each
time we delete a vertex $v$ that currently holds $s$ primary tokens (for some
$s\geqslant 1$), $v$ gives to each of its neighbors later in $\sigma$ exactly
$s$ “secondary” tokens; see Figure 7.

2453671245367black1black1453671 black21 black2black1$\downarrow$45671 black2
31 black2black3black15671 black2 3 black42 black3 4black1672 black3 4 5 black1
2 4 black57black1 2 3 4 black5
6$\leftarrow$$\leftarrow$$\leftarrow$$\rightarrow$$\rightarrow$ Figure 7: A
portion of a 2-degenerate graph $G$ and the positions of its tokens as its
vertices are deleted in a 2-degeneracy order; here $S=\\{1,\ldots,7\\}$. The
number of each token indicates the vertex where the token originated. Primary
tokens are shown in bold. At each vertex, we show at most one token received
from each other vertex, giving preference to primary tokens.

We will analyze this process to show that all but a constant number of
vertices in $S$ induce an independent set. That is, there exists
$\widehat{S}\subseteq S$, of bounded size, such that $S\setminus\widehat{S}$
is an independent set. Furthermore, we can modify $G$, $S$, and $\sigma$ to
get a graph $G^{\prime}$ that is 2-degenerate, as witnessed by a vertex order
$\sigma^{\prime}$, and $G^{\prime}$ is nice w.r.t. a clique $S^{\prime}$ in
$(G^{\prime})^{2}$. Finally, $|S|-|S^{\prime}|\leqslant c$. Let
$\textrm{tokens}(v)$††margin:  $\textrm{tokens}(v)$ (resp.
$\textrm{primary}(v)$††margin:  $\textrm{primary}(v)$ ) denote the number of
tokens (resp. primary tokens) that each vertex $v$ holds immediately before it
is deleted.

######  Claim 3.1.

If $v\in S$ and $w_{1},w_{2}$ are the neighbors of $v$ later in $\sigma$, if
they exist, then

$1+\textrm{tokens}(v)+D+\textrm{primary}(w_{1})+\textrm{primary}(w_{2})+6\geqslant|S|\geqslant\frac{5}{2}D+60.$
($\star$)

Proof. Fix $v\in S$. Recall that $v$ must be adjacent in $G^{2}$ to every
vertex in $S$. Each neighbor $w$ of $v$ that precedes $v$ in $\sigma$ can be
the source of at most one such adjacency in $G^{2}$ to a vertex $x$ from which
$v$ receives no token (neither primary nor secondary), so in total $v$ can
have at most $D$ such adjacencies. Each other adjacency in $G^{2}$ must be
accounted for either (a) by a token received by $v$ or (b) by a primary token
that has been or will be received by $w_{1}$ or $w_{2}$ or (c) by being an
adjacency to $w_{1}$ or $w_{2}$ or to a neighbor of some $w_{i}$ that comes
later than $w_{i}$ in $\sigma$. At most $\textrm{tokens}(v)$ vertices of $S$
are handled by (a), and at most 6 vertices of $S$ are handled by (c). The
number handled by (b) is at most
$\textrm{primary}(w_{1})+\textrm{primary}(w_{2})$. This implies ($\star$ ‣
3.1).  $\diamondsuit$

To analyze the movement of tokens, we use the following definitions (all
w.r.t. $G$, $S$, and $\sigma$). Let
$\emph{{Big}}\marginpar{\normalcolor\raggedright\scriptsize{\textsc{Big}}}:=\\{v\in
V(G):\textrm{primary}(v)>\frac{1}{4}D\\}\@add@raggedright$. Let
$\emph{{Basic}}\marginpar{\normalcolor\raggedright\scriptsize{\textsc{Basic}}}:=\\{v\in
S:\textrm{tokens}(v)<\frac{1}{4}D\\}\@add@raggedright$. Let
$\emph{{NonBasic}}\marginpar{\normalcolor\raggedright\scriptsize{\textsc{NonBasic}}}:=S\setminus\textsc{Basic}\@add@raggedright$.
So $\textsc{Big}\cap\textsc{Basic}=\emptyset$. And possibly both
$\textsc{Big}\not\subseteq\textsc{NonBasic}$ and
$\textsc{NonBasic}\not\subseteq\textsc{Big}$. Note that each vertex $v$ gives
primary tokens to at most two vertices, and each of those vertices gives
secondary tokens (due to $v$) to at most two more vertices. Thus, $v$
contributes at most 6 to the total number of tokens held by vertices at any
point. So $\sum_{v\in V(G)}\textrm{tokens}(v)\leqslant 6|S|\leqslant
6f(D)\leqslant 18D$. Thus, we get that
$|\textsc{NonBasic}\cup\textsc{Big}|\leqslant 18D/(D/4)=72$. We will later
refine this argument to get a stronger upper bound.

######  Claim 3.2.

Each vertex $v\in\textsc{Basic}$ has two neighbors later in $\sigma$ that are
both in Big.

Proof. Let $w_{1},w_{2}$ be the neighbors of $v$ later in $\sigma$, if they
exist. Inequality ($\star$ ‣ 3.1) simplifies to
$\textrm{tokens}(v)+\textrm{primary}(w_{1})+\textrm{primary}(w_{2})\geqslant\frac{3}{2}D+53$.
Since $v$ is basic, we have $\textrm{tokens}(v)<\frac{1}{4}D$. So
$\textrm{primary}(w_{1})+\textrm{primary}(w_{2})\geqslant\frac{5}{4}D+53$.
Clearly, $\textrm{primary}(w_{i})\leqslant D$ for each $i\in\\{1,2\\}$, which
implies that also $\textrm{primary}(w_{i})\geqslant\frac{1}{4}D+53$, for each
$i\in\\{1,2\\}$. So $w_{1},w_{2}\in\textsc{Big}$.  $\diamondsuit$

Let $\emph{W}\marginpar{\normalcolor\raggedright\scriptsize{W}}:=\\{w:w\in
N(v)\@add@raggedright$ for some $v\in\textsc{NonBasic}$ and $w$ appears later
in $\sigma$ than $v$}.

######  Claim 3.3.

If some vertex $w$ comes after the first vertex in $S$ and
$w\notin\textsc{Big}$, then $w\in W$.

Proof. Since $G$ minimizes $|V(G)|+|E(G)|$, every edge has an endpoint in $S$.
Since $\sigma$ puts the first vertex $v$ of $S$ as late as possible, every
vertex $w$ after $v$ is a later neighbor of some vertex $x\in S$. Every vertex
in Basic has as its later neighbors in $\sigma$ exactly two vertices in Big,
by Claim 3.2. Thus, if $w\notin\textsc{Big}$, then $x\in\textsc{NonBasic}$;
hence, by definition, $w\in W$.  $\diamondsuit$

Now we modify $G$, $S$, $\sigma$ to construct _$G^{\prime}$ , $S^{\prime}$,
$\sigma^{\prime}$_††margin:  $G^{\prime}$, $S^{\prime}$, $\sigma^{\prime}$ .

  1. (1)

Let $S^{\prime}:=\textsc{Basic}\setminus W$.

  2. (2)

Move Big to the end of $\sigma$ (after the final vertex of $S^{\prime}$) and
move $(\textsc{NonBasic}\cup W)\setminus\textsc{Big}$ to the start of $\sigma$
(before the first vertex of $S^{\prime}$); call the resulting order
$\sigma^{\prime}$.

  3. (3)

Delete every edge of $G$ with both endpoints outside $S^{\prime}$; call the
resulting graph $G^{\prime}$.

Now we check that $G^{\prime}$, $S^{\prime}$, $\sigma^{\prime}$ satisfy the
desired criteria.

######  Claim 3.4.

$S^{\prime}$ appears consecutively in $\sigma^{\prime}$, and $S^{\prime}$ and
$V(G^{\prime})\setminus S^{\prime}$ are each independent in $G^{\prime}$.

Proof. By Claim 3.2, every vertex of $S^{\prime}$ has two later neighbors in
Big. And every vertex $v$ of Big has no later neighbors. (Such a neighbor $w$
would have $\textrm{tokens}(w)>\frac{1}{4}D$, so $w$ would be excluded from
Basic, and hence from $S^{\prime}$. Thus, edge $vw$ would be removed in (3).)
So Big comes, in some order, at the end of $\sigma^{\prime}$. And every vertex
not in $S^{\prime}\cup\textsc{Big}$ has no earlier neighbors in $S^{\prime}$,
so comes before the first vertex of $S^{\prime}$ in $\sigma^{\prime}$ (by
Claim 3.3 and (2) above); thus, $S^{\prime}$ is consecutive in
$\sigma^{\prime}$. To see that $S^{\prime}$ is an independent set in
$G^{\prime}$, note that every vertex in Basic has two later neighbors in Big.
But $S^{\prime}\subseteq\textsc{Basic}$, so
$S^{\prime}\cap\textsc{Big}\subseteq\textsc{Basic}\cap\textsc{Big}=\emptyset$.
Thus, $S^{\prime}$ is independent. Finally, $V(G^{\prime})\setminus
S^{\prime}$ is independent in $G^{\prime}$ by step (3) above constructing
$G^{\prime}$.  $\diamondsuit$

######  Claim 3.5.

$G^{\prime}$ is $2$-degenerate, as witnessed by $\sigma^{\prime}$.

Proof. Consider steps (2) and (3) above. Suppose we move some
$v\in\textsc{Big}$ to the end of $\sigma$. If $v$ has a neighbor $w$ later (in
$\sigma$), then $w\notin\textsc{Basic}$, so $w\notin S^{\prime}$. Thus, in
step (3) we delete edge $vw$. Suppose instead that we move a vertex
$v\in(\textsc{NonBasic}\cup W)\setminus\textsc{Big}$ to the start of $\sigma$.
If $v$ has a neighbor $w$ earlier (in $\sigma$), then $w\notin\textsc{Basic}$,
by Claim 3.4; so $w\notin S^{\prime}$. Thus, again in step (3) we delete $vw$.
So $\sigma^{\prime}$ is a 2-degeneracy order for $G^{\prime}$ because $\sigma$
is a 2-degeneracy order for $G$.  $\diamondsuit$

######  Claim 3.6.

$S^{\prime}$ forms a clique in $G^{\prime 2}$.

Proof. Every edge deleted when forming $G^{\prime}$ has both endpoints outside
of $S^{\prime}$. But deleting such edges cannot impact adjacency in $G^{\prime
2}$ between two vertices in $S^{\prime}$. Thus, $G^{\prime
2}[S^{\prime}]=G^{2}[S^{\prime}]$.  $\diamondsuit$

######  Claim 3.7.

$|S\setminus S^{\prime}|\leqslant 72$. More strongly (for $D\geqslant 144$),
we have $|S\setminus S^{\prime}|\leqslant 60+12\times(144/D)$.

Proof. Let _$X$_ ††margin:  $X$ $:=\textsc{Big}\cup\textsc{NonBasic}\cup W$
and note from (1) that $|S\setminus S^{\prime}|\leqslant|X|$. To bound the
size of $X$, we use a discharging argument. Every vertex $x\in X$ begins with
charge $\textrm{tokens}(x)$. We consider each
$x\in\textsc{Big}\cup\textsc{NonBasic}$ (note that this union does not include
$W$) and redistribute charge so that $x$, $w_{1}$, and $w_{2}$ all finish with
charge at least $\frac{1}{4}D$; again, $w_{1}$ and $w_{2}$ are the neighbors
of $x$ that follow $x$ in $\sigma$ (if they exist). Recall that $\sum_{v\in
V(G)}\textrm{tokens}(v)\leqslant 6|S|\leqslant 18D$. Thus, this proves that
$|S\setminus S^{\prime}|\leqslant|X|\leqslant 6|S|/(D/4)\leqslant
18D/(D/4)=72$.

Fix $x\in\textsc{Big}$. By definition, $\textrm{primary}(x)>\frac{1}{4}D$.
Further, $\textrm{tokens}(w_{i})\geqslant\textrm{primary}(x)>\frac{1}{4}D$ for
each $i\in\\{1,2\\}$. So $x$ does not need to give charge to any neighbor
later in $\sigma$. Thus, $x$ (and each of its later neighbors) finishes with
charge at least $\frac{1}{4}D$.

Fix $x\in(\textsc{NonBasic}\setminus\textsc{Big})$. If
$\textrm{tokens}(x)\geqslant\frac{3}{4}D$, then $x$ gives charge
$\frac{1}{4}D$ to each of its at most two neighbors that follows it in
$\sigma$. Suppose instead that
$\frac{1}{2}D\leqslant\textrm{tokens}(x)<\frac{3}{4}D$. By ($\star$ ‣ 3.1), we
have $\textrm{primary}(w_{1})+\textrm{primary}(w_{2})>\frac{3}{4}D$. So
clearly $\textrm{primary}(w_{i})>\frac{1}{4}D$ for some $i\in\\{1,2\\}$. Thus,
at least one later neighbor of $x$ is big. So $x$ gives charge $\frac{1}{4}D$
to at most one neighbor later in $\sigma$. Thus, $x$ (and each of its later
neighbors) finishes with charge at least $\frac{1}{4}D$.

Finally, suppose that $\frac{1}{4}D\leqslant\textrm{tokens}(x)<\frac{1}{2}D$.
So ($\star$ ‣ 3.1) gives $\textrm{primary}(w_{1})+\textrm{primary}(w_{2})>D$.
Thus, $w_{i}\in\textsc{Big}$ for at least one $i\in\\{1,2\\}$, so $w_{i}$
needs no charge from $x$. If $w_{1},w_{2}\in\textsc{Big}$, then neither
$w_{i}$ receives charge from $x$, so $x$ (and each $w_{i}$) finishes with
charge at least $\frac{1}{4}D$. Suppose instead, by symmetry, that
$w_{1}\in\textsc{Big}$ and $w_{2}\notin\textsc{Big}$. Since
$\textrm{primary}(w_{1})\leqslant D$, we know that
$\textrm{tokens}(x)+\textrm{primary}(w_{2})\geqslant\frac{1}{2}D$. Thus, $x$
gives to $w_{2}$ charge $\textrm{tokens}(x)-\frac{1}{4}D$. Clearly $x$
finishes with charge at least $\frac{1}{4}D$. Furthermore, $w_{2}$ ends with
charge at least
$\textrm{primary}(w_{2})+(\textrm{tokens}(x)-\frac{1}{4}D)\geqslant\frac{1}{2}D-\frac{1}{4}D=\frac{1}{4}D$.

Thus, each vertex of $X$ finishes with charge at least $\frac{1}{4}D$. Hence,
$|S\setminus S^{\prime}|\leqslant|X|\leqslant 6|S|/(D/4)\leqslant
18D/(D/4)=72$, as claimed. Combining this with Theorem 3 gives
$|S|\leqslant\frac{5}{2}D+72$. Substituting this bound into the previous
inequality gives $|X|\leqslant 6|S|/(D/4)\leqslant(15D+6\times
72)/(D/4)=60+(12\times 144)/D$.  $\diamondsuit$

Claims 3.4–3.7 show $c=72$ suffices. When $D>12\times 144$, Claim 3.7 shows
$c=60$ suffices. ∎

##  4 Big Cliques in Squares of Graphs with Mad $\boldsymbol{<4}$

In this section, we extend the main result of Section 3 from the class of
2-degenerate graphs to the class of graphs with maximum average degree less
than 4. To formalize this idea, we use the following definition. Fix a
positive integer $D$. Let _$g(D)$_ ††margin:  $g(D)$ be the maximum size of a
clique in the square of a graph $G$ with $\textrm{mad}(G)<4$ and
$\Delta(G)\leqslant D$. Recall, from Section 3, that $f(D)$ is defined as the
analogous maximum over 2-degenerate graphs. Since every 2-degenerate graph $G$
has $\textrm{mad}(G)<4$, clearly $f(D)\leqslant g(D)$. In this section we show
that also $g(D)-f(D)$ is bounded by a small constant. We formalize this result
as follows.

######  Theorem 6.

There exists a constant $c$ such that for every positive integer $D$ some
2-degenerate graph $G$ with $\Delta(G)\leqslant D$ has a clique $S^{\prime}$
in $G^{2}$ with $|S^{\prime}|\geqslant g(D)-c$. In fact, $c=460$ suffices.

We have made very little effort to minimize $c$ (so it is likely far from
sharp), prefering to present a simpler proof. Before proving Theorem 6, we
recall a result of Hocquard, Kim, and Pierron which slightly simplifies our
proof. If we instead want to avoid using this result, we can just observe that
$G$ is 3-degenerate, so $G^{2}$ is $5D$-degenerate, which results in a larger
value of $c$.

######  Theorem A ([11]).

If $G$ is a graph with $\Delta(G)\leqslant D$ and $\textrm{mad}(G)<4$, then
$G^{2}$ has degeneracy at most $3D$. In particular, $\omega(G^{2})\leqslant
3D+1$.

###### Proof of Theorem 6..

Fix $D$††margin:  $D$, $G$ and let $G$ be a graph with $\Delta(G)\leqslant D$
and $\textrm{mad}(G)<4$ such that $G^{2}$ contains a clique _$S$_ ††margin:
$S$ of order $g(D)$. Subject to this, choose $G$ to minimize $|V(G)|+|E(G)|$.
As a result, $V(G)\setminus S$ is an independent set. We assume that
$g(D)\geqslant\frac{5}{2}D+60$; otherwise, we are done (for this choice of
$D$) with $c=60$ by Example 1. Since $\textrm{mad}(G)<4$, the graph $G$ has a
3-degeneracy order _$\sigma$_ ††margin:  $\sigma$ . Let _$R_{3}$_ ††margin:
$R_{3}$ be the subset of $V(G)\setminus S$ each with at least 3 neighbors in
$S$.

######  Claim 4.1.

$|R_{3}|<2|S|$.

Proof. Let $G_{1}:=G[S\cup R_{3}]$. Clearly $\sum_{v\in
V(G_{1})}d_{G_{1}}(v)\geqslant 6|R_{3}|$. So
$6|R_{3}|/(|S|+|R_{3}|)\leqslant\textrm{mad}(G_{1})\leqslant\textrm{mad}(G)<4$.
That is, $6|R_{3}|<4|S|+4|R_{3}|$, which proves the claim.  $\diamondsuit$

We pass tokens similarly to the way we did in Section 3, with an added wrinkle
for vertices in $R_{3}$. Just before it is deleted, each $v\in S$ passes a
“primary” token to each of its neighbors later in $\sigma$. Again, if a vertex
$v$ is holding $s$ primary tokens just before it is deleted, then $v$ passes
$s$ “secondary” tokens to each of its neighbors later in $\sigma$ (for every
$s\geqslant 1$). Finally, if some $v\in R_{3}$ has 3 neighbors in $S$ later in
$\sigma$, then $v$ passes a “tertiary” token to each of these neighbors.
Again, let $\textrm{tokens}(v)$††margin:  $\textrm{tokens}(v)$ (resp.
$\textrm{primary}(v)$††margin:  $\textrm{primary}(v)$ ) denote the number of
tokens (resp. primary tokens) that each vertex $v$ holds immediately before it
is deleted (note that $\textrm{tokens}(v)$ now counts _tertiary_ tokens, as
well as primary and secondary tokens). Our next claim is nearly identical to
one in the previous section.

######  Claim 4.2.

If $v\in S$ and $w_{1},w_{2},w_{3}$ are the neighbors of $v$ later in
$\sigma$, if they exist, then

$1+\textrm{tokens}(v)+D+\textrm{primary}(w_{1})+\textrm{primary}(w_{2})+\textrm{primary}(w_{3})+12\geqslant|S|\geqslant
5D/2+60.$ ($\star\star$)

Proof. Fix $v\in S$. Recall that $v$ must be adjacent in $G^{2}$ to every
vertex in $S$. Each neighbor $w$ of $v$, with $w\notin R_{3}$, that precedes
$v$ in $\sigma$ is the source of at most one such adjacency in $G^{2}$ to a
vertex $x$ from which $v$ receives no token (neither primary, nor secondary,
nor tertiary); if $w\in R_{3}$, then it can create two adjacencies for $v$ in
$G^{2}$, but one of these is accounted for by a tertiary token sent to $v$. So
in total $v$ has at most $D$ such adjacencies (that send no tokens to $v$).

Each other adjacency in $G^{2}$ must be accounted for either (a) by a token
received by $v$ or (b) by a primary token that has been or will be received by
$w_{1}$ or $w_{2}$ or $w_{3}$ or (c) by being an adjacency to $w_{1}$ or
$w_{2}$ or $w_{3}$, or to a neighbor of some $w_{i}$ that comes later than
$w_{i}$ in $\sigma$. At most $\textrm{tokens}(v)$ vertices of $S$ are handled
by (a), and at most $3+3^{2}=12$ vertices of $S$ are handled by (c). The
number handled by (b) is at most
$\textrm{primary}(w_{1})+\textrm{primary}(w_{2})+\textrm{primary}(w_{3})$.
This implies ($\star\star$ ‣ 4.2).  $\diamondsuit$

Similarly to what we did in Section 3, we let
$\emph{{Big}}\marginpar{\normalcolor\raggedright\scriptsize{\textsc{Big}}}:=\\{v\in
V(G):\textrm{primary}(v)>\frac{1}{8}D\\}\@add@raggedright$, we let
$\emph{{Basic}}\marginpar{\normalcolor\raggedright\scriptsize{\textsc{Basic}}}:=\\{v\in
S:\textrm{tokens}(v)<\frac{1}{4}D\\}\@add@raggedright$ and we let
$\emph{{NonBasic}}\marginpar{\normalcolor\raggedright\scriptsize{\textsc{NonBasic}}}:=S\setminus\textsc{Basic}\@add@raggedright$.
If $D\leqslant 2$, then $g(D)\leqslant 5$, and we are done; so instead assume
$D\geqslant 3$. Note that $|\textsc{Big}|\leqslant 3|S|/(D/8)\leqslant
3(3D+1)/(D/8)=72+24/D\leqslant 80$; the first inequality here uses Theorem A.
The total number of primary and secondary tokens is at most $(3+3^{2})|S|$,
and the total number of tertiary tokens is at most $3|R_{3}|<6|S|\leqslant
18D+3$. So the total number of tokens is, by Claim 4.1, at most
$12|S|+3|R_{3}|<18|S|\leqslant 54D+3$. Thus,
$|\textsc{NonBasic}|\leqslant(54D+3)/(D/4)=216+12/D\leqslant 220$.

######  Claim 4.3.

Every vertex $v\in\textsc{Basic}$ has at least two neighbors in Big (that are
later in $\sigma$).

Proof. If $v\in\textsc{Basic}$, then $\textrm{tokens}(v)<\frac{1}{4}D$, so
($\star\star$ ‣ 4.2) implies
$\textrm{primary}(w_{1})+\textrm{primary}(w_{2})+\textrm{primary}(w_{3})\geqslant\frac{5}{4}D$.
By symmetry, assume
$\textrm{primary}(w_{1})\geqslant\textrm{primary}(w_{2})\geqslant\textrm{primary}(w_{3})$.
By Pigeonhole, $\textrm{primary}(w_{1})>\frac{1}{8}D$, so
$w_{1}\in\textsc{Big}$. Clearly, $\textrm{primary}(w_{1})\leqslant D$. Thus,
$\textrm{primary}(w_{2})+\textrm{primary}(w_{3})\geqslant\frac{1}{4}D$. Again,
by Pigeonhole, $\textrm{primary}(w_{2})\geqslant\frac{1}{8}D$, so also
$w_{2}\in\textsc{Big}$.  $\diamondsuit$

Let
$R:=\\{v\notin\textsc{Big}:|N(v)\cap(\textsc{Big}\cup\textsc{Basic})|\geqslant
3\\}$ and $S^{+}:=\textsc{Basic}\cup\textsc{Big}$.††margin:  $R$, $S^{+}$

######  Claim 4.4.

We have $\sum_{v\in R}(d_{S^{+}}(v)-2)<2|\textsc{Big}|$.

Proof. Let $S^{-}:=\textsc{Basic}\setminus(R\cup\textsc{Big})$ and
$G_{2}:=G[\textsc{Basic}\cup R\cup\textsc{Big}]$. Note that $\sum_{v\in
V(G_{2})}d_{G_{2}}(v)\geqslant 4|S^{-}|+2\sum_{v\in R}d_{S^{+}}(v)$, by Claim
4.3. Thus, $4>\textrm{mad}(G_{2})\geqslant(4|S^{-}|+2\sum_{v\in
R}d_{S^{+}}(v))/(|S^{-}|+|R|+|\textsc{Big}|)$. So $4|S^{-}|+2\sum_{v\in
R}d_{S^{+}}(v)<4(|S^{-}|+|R|+|\textsc{Big}|)$, which proves the claim.
$\diamondsuit$

Let _$S^{\prime}$_ ††margin:  $S^{\prime}$
$:=\textsc{Basic}\setminus\textsc{Big}$. (Unlike in Section 3, here possibly
$\textsc{Basic}\cap\textsc{Big}\neq\emptyset$.)

We form $G^{\prime}$, $S^{\prime}$, $\sigma^{\prime}$ from $G$, $S$, $\sigma$,
as follows.

  1. (1)

Move Big to the end of the order, and delete all edges with neither endpoint
in $S^{\prime}$.

  2. (2)

For each vertex $v\notin S^{\prime}\cup\textsc{Big}$, delete all but two edges
incident to $v$, and move $v$ to the start of the order; remove all endpoints
of those deleted edges from $S^{\prime}$.

  3. (3)

Now consider $v\in S^{\prime}$; by (2), every neighbor of $v$ later in the
order is in $S^{\prime}\cup\textsc{Big}$. If $v$ has at most two neighbors
later in the order, then do nothing. Otherwise, delete all but two edges from
$v$ to neighbors later in the order; in particular, delete edges from $v$ to
two big neighbors. Remove from $S^{\prime}$ vertex $v$ and any endpoints of
deleted edges that were in $S^{\prime}$.

Denote by $G^{\prime}$ the graph resulting from the process above. The
resulting order $\sigma^{\prime}$ is a 2-degeneracy order for $G^{\prime}$,
and $S^{\prime}$ induces a clique in $G^{\prime 2}$. All that remains is to
show that
$|S^{\prime}|\geqslant|S|-|\textsc{NonBasic}|-3|\textsc{Big}|\geqslant|S|-220-3\times
80=|S|-460$.

Before (1) above, we have
$|S^{\prime}|\geqslant|\textsc{Basic}|-|\textsc{Big}|=|S|-|\textsc{NonBasic}|-|\textsc{Big}|$.
It is straightforward to check that for each vertex $v$ considered in (2) and
(3), all its neighbors later in the order are in $S^{+}$. Further, the
decrease in $|S^{\prime}|$ when we process $v$ is at most
$\max\\{0,d_{S^{+}}(v)-2\\}$. Thus, the total decrease in $|S^{\prime}|$ from
(2) and (3) is at most $\sum_{v\in
V(G)\setminus\textsc{Big}}\max\\{0,d_{S^{+}}(v)-2\\}=\sum_{v\in
R}(d_{S^{+}}(v)-2)<2|\textsc{Big}|$, by Claim 4.4. So
$|S^{\prime}|\geqslant|S|-|\textsc{NonBasic}|-3|\textsc{Big}|\geqslant|S|-460$.
∎

##  5 Open Questions

In this paper we have determined, among graphs with maximum degree at most
$D$, the maximum order of a clique in $G^{2}$, up to an additive constant, (a)
when $G$ is 2-degenerate and (b) when $\textrm{mad}(G)<2\times 2$. Recall that
$f(D)$ and $g(D)$ are the largest possible sizes of a clique in $G^{2}$ when
$G$ has maximum degree at most $D$ and satisfies (a) and (b), respectively. It
is natural to ask when $g(D)=f(D)$.

######  Question 1.

For which positive integers $D$ does $g(D)=f(D)$?

We can ask analogous questions for larger values of degeneracy or maximum
average degree.

######  Question 2.

For each positive integer $k$, what is the minimum value $\alpha_{k}$††margin:
$\alpha_{k}$, $c_{k}$ such that there exists a constant $c_{k}$ such that if
$G$ is $k$-degenerate with maximum degree at most $D$, then
$\omega(G^{2})\leqslant\alpha_{k}D+c_{k}$?

Recall that if $G$ is $k$-degenerate with $\Delta(G)\leqslant D$, then $G^{2}$
has degeneracy at most $(2k-1)D-k^{2}$; this is witnessed by any order
witnessing that $G$ is $k$-degenerate. Thus, $\alpha_{k}\leqslant 2k-1$. By
extending the ideas in Example 2, we can also construct such graphs $G$ for
which the degeneracy of $G^{2}$ is equal to $(2k-1)D-k^{2}$; see Example 3
below. However, we believe that $\alpha_{k}<2k-1$. In fact, it is interesting
to ask about $\lim_{k\to\infty}(2k-1)-\alpha_{k}$ and
$\lim_{k\to\infty}(2k-1)/\alpha_{k}$. We suspect the first limit is infinite,
but do not have a conjectured value for the second limit.

Now we consider the larger class of graphs with $\textrm{mad}(G)<2k$.

######  Question 3.

For each positive integer $k$, what is the minimum value $\beta_{k}$††margin:
$\beta_{k}$, $d_{k}$ such that there exists a constant $d_{k}$ such that if
$\textrm{mad}(G)<2k$ and $G$ has maximum degree at most $D$, then
$\omega(G^{2})\leqslant\beta_{k}D+d_{k}$?

If $\textrm{mad}(G)<2k$, then $G$ has degeneracy at most $2k-1$. Thus, by the
argument above, $\beta_{k}\leqslant 2(2k-1)-1=4k-3$. This was significantly
improved by Kierstead et al. [13] who showed that if $\Delta(G)\leqslant D$
and $2(k-1)<\textrm{mad}(G)\leqslant 2k$, then $G^{2}$ has degeneracy at most
$(2k-1)D+2k$. Thus, $\beta_{k}\leqslant 2k-1$. In this paper, we proved
$\alpha_{2}=\beta_{2}=5/2$. We believe this equality persists for larger
values of $k$, but in general we have no conjecture for the precise value of
$\alpha_{k}$ (and $\beta_{k}$).

######  Conjecture 1.

For all $k\geqslant 2$, we have $\beta_{k}=\alpha_{k}$.

In any future efforts to improve the upper bounds on $\alpha_{k}$ and
$\beta_{k}$, it would be natural to try a token passing scheme, similar to
what we used in Sections 3 and 4.

This paper was motivated by a question of Hocquard, Kim, and Pierron: Given a
positive integer $D$, what is the maximum value of $\chi(G^{2})$ over all
graphs $G$ with maximum degree $D$ such that (a) $G$ is 2-degenerate or (b)
$\textrm{mad}(G)<4$. It is natural to generalize these questions.

######  Question 4.

Fix positive integers $D$ and $k$. (a) What is the maximum value of
$\chi(G^{2})$ over all graphs $G$ with maximum degree $D$ that are
$k$-degenerate? (b) What is the maximum value of $\chi(G^{2})$ over all graphs
$G$ with maximum degree $D$ such that $\textrm{mad}(G)<2k$?

In an effort to attack Question 4, it would be natural to try to improve the
degeneracy bound for $G^{2}$, mentioned above, proved by Kierstead et al. We
end this short section by observing that this bound is nearly the best
possible. Essentially, we generalize Example 2 to $k$-degenerate graphs for
each larger $k$. (Recall that each $k$-degenerate graph $G$ has
$\textrm{mad}(G)<2k$.) For the proof, we will use the following well-known
result of Hajnal and Szemerédi [8].

######  Hajnal–Szemerédi Theorem ([8]).

If $G$ is a graph with $|V(G)|=(k+1)r$ and $\Delta(G)\leqslant k$, for
positive integers $r$ and $k$, then $G$ has a proper coloring with $k+1$ color
classes each of size $r$.

######  Example 3.

For all integers $k$ and $D$ with $D\geqslant k\geqslant 2$, we can construct
a graph $H_{D,k}$ that is $k$-degenerate with maximum degree $D$ but such that
$H_{D,k}^{2}$ is not $((2k-1)D-k^{2}-1)$-degenerate.

We essentially generalize Example 2. We want to partition some $S\subseteq
V(G)$ into parts of size $D$ and repeat this step $k$ times, with no two
vertices in the same part in more than one step. Afterward, we want to
partition $S$ into parts of size $k$, repeated $D-k$ times, such that each
pair of vertices appears in a common part (over all $k+(D-k)$ times) at most
once. In fact, all of this can be done by repeated application of the
Hajnal–Szemerédi Theorem.

Fix a set $S$ s.t. $|S|=2kD^{2}$. We will build a graph $G$ with $S\subseteq
V(G)$ and also build an auxiliary graph $J$ with $V(J)=S$, which will aid in
the construction of $G$. (At the end, we will let $H_{D,k}:=G$.) Initially,
let $V(G)=V(J)=S$ and $E(G)=E(J)=\emptyset$. Trivially, we can partition
$V(J)$ into $|S|/D$ independent sets, each of size $D$. For each part $P_{i}$
in this partition, add to $G$ a vertex $w_{i}$ adjacent to precisely the
vertices in $P_{i}$. Moreover, add to $E(J)$ the edge $vv^{\prime}$ for each
pair $v,v^{\prime}$ in a common part. Now we again partition $V(J)$ into
$|S|/D$ independent sets, each of size $D$; this time we use Hajnal–Szemerédi.
We repeat this process, partitioning $V(J)$ a total of $k$ times, each time
into $|S|/D$ parts, and each inducing no edges. After each partition, we add
the prescribed edges to $E(J)$ and $E(G)$. This ensures that each pair of
vertices in $S$ appear in a common part in at most one partition. In a second
phase we partition $|S|$ into parts of size $k$, and we do this $D-k$ times.
After the final partition, the degree of each vertex in $J$ is exactly
$k(D-1)+(D-k)(k-1)\leqslant D(2k-1)$. Thus, $H^{2}_{D,k}[S]$ has minimum
degree $k(D-1)+(D-k)(k-1)$. We do not really care about the number of color
classes, just that the size of each is $D$ (in the first phase) or $k$ (in the
second phase). Although we required above that $|S|=2kD^{2}$, we note that the
same construction works whenever $|S|\geqslant 2kD^{2}$ and $kD\big{|}|S|$.

Let $H_{D,k}:=G$. We verify, as follows, that $H_{D,k}$ is $k$-degenerate.
Each vertex $w_{i}$ arising from a part of size $k$ has degree exactly $k$. So
all of these $w_{i}$ can be deleted first. Next, we can delete all vertices of
$S$, since each of them has exactly $k$ remaining neighbors. Finally, we can
delete all vertices $w_{i}$ arising from parts of size $D$ (which form an
independent set). $\diamondsuit$

## References

  * [1] O. Amini, L. Esperet, and J. van den Heuvel.  A unified approach to distance-two colouring of graphs on surfaces.  Combinatorica, 33(3):253–296, 2013, arXiv:0812.1345.
  * [2] M. Bonamy, T. Perrett, and L. Postle.  Colouring graphs with sparse neighbourhoods: bounds and applications.  J. Combin. Theory Ser. B, 155:278--317, 2022, arXiv:1810.06704.
  * [3] H. Bruhn and F. Joos.  A stronger bound for the strong chromatic index.  Combin. Probab. Comput., 27(1):21--43, 2018, arXiv:1504.02583.
  * [4] F. R. K. Chung, A. Gyárfás, Z. Tuza, and W. T. Trotter.  The maximum number of edges in $2K_{2}$-free graphs of bounded degree.  Discrete Math., 81(2):129--135, 1990.
  * [5] D. W. Cranston.  Coloring, list coloring, and painting squares of graphs (and other related problems).  Electron. J. Combin., DS25 (Dynamic Surveys):42, 2023, arXiv:2210.05915.
  * [6] D. W. Cranston.  Bounding Clique Size in Squares of Planar Graphs.  Eur. J. Combin. 120 (2024), Paper No. 103960. arXiv:2308.09585.
  * [7] M. Faron and L. Postle.  On the clique number of the square of a line graph and its relation to maximum degree of the line graph.  J. Graph Theory, 92(3):261--274, 2019, arXiv:1708.02264.
  * [8] A. Hajnal and E. Szemerédi.  Proof of a conjecture of P. Erdős.  In Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), pages 601--623. North-Holland, Amsterdam, 1970.
  * [9] S. G. Hartke, S. Jahanbekam, and B. Thomas.  The chromatic number of the square of subcubic planar graphs.  2016, arXiv:1604.06504.
  * [10] F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed.  List colouring squares of planar graphs.  2007, arXiv:0807.3233.
  * [11] H. Hocquard, S.-J. Kim, and T. Pierron.  Coloring squares of graphs with mad constraints.  Discrete Appl. Math., 271:64--73, 2019, arXiv:1902.08135.
  * [12] E. Hurley, R. de Joannis de Verclos, and R. J. Kang.  An improved procedure for coloring graphs of bounded local density.  Advances in Combinatorics, 7, 2022, arXiv:2007.07874.
  * [13] H. A. Kierstead, D. Yang, and J. Yi.  On coloring numbers of graph powers.  Discrete Math., 343(6):111712, 7, 2020, arXiv:1907.10962.
  * [14] S.-J. Kim and X. Lian.  Tight upper bound on the clique size in the square of 2-degenerate graphs. arXiv:2311.02914.
  * [15] M. Śleszyńska-Nowak.  Clique number of the square of a line graph.  Discrete Math., 339(5):1551--1556, 2016, arXiv:1504.06585.
  * [16] C. Thomassen.  The square of a planar cubic graph is 7-colorable.  J. Combin. Theory Ser. B, 128:192--218, 2018, arXiv:1708.04406.