# Strong cliques and forbidden cycles

Wouter Cames van Batenburg, Ross Kang, François Pirot

► To cite this version:

Wouter Cames van Batenburg, Ross Kang, François Pirot. Strong cliques and forbidden cycles. Indagationes Mathematicae, 2020, 31 (1), pp.64-82. 10.1016/j.indag.2019.09.003. hal-04245515

HAL Id: hal-04245515

https://hal.science/hal-04245515v1

Submitted on 12 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Strong cliques and forbidden cycles

Wouter Cames van Batenburg *

François Pirot ‡

Ross J. Kang †

November 25, 2021

**Abstract**

Given a graph $G$, the strong clique number $\omega_2'(G)$ of $G$ is the cardinality of a largest collection of edges every pair of which are incident or connected by an edge in $G$. We study the strong clique number of graphs missing some set of cycle lengths. For a graph $G$ of large enough maximum degree $\Delta$, we show among other results the following: $\omega_2'(G) \le 5\Delta^2/4$ if $G$ is triangle-free; $\omega_2'(G) \le 3(\Delta - 1)$ if $G$ is $C_4$-free; $\omega_2'(G) \le \Delta^2$ if $G$ is $C_{2k+1}$-free for some $k \ge 2$. These bounds are attained by natural extremal examples. Our work extends and improves upon previous work of Faudree, Gyárfás, Schelp and Tuza (1990), Mahdian (2000) and Faron and Postle (2019). We are motivated by the corresponding problems for the strong chromatic index.

**Keywords:** strong clique number, strong chromatic index, forbidden cycles.

# 1 Introduction

A strong edge-colouring of a graph $G$ is a partition of the edges $E(G)$ into parts each of which induces a matching; the strong chromatic index $\chi_2'(G)$ of $G$ is the least number of parts in such a partition. Although easily defined, $\chi_2'$ has proven very difficult to analyse: a conjecture of Erdős and Nešetřil [2] from the 1980s is notorious. ($\Delta_G$ denotes the maximum degree of $G$.)

**Conjecture 1 ([2]).** For a graph $G$ with $\Delta_G = \Delta$, $\chi_2'(G) \le \frac{5}{4}\Delta^2$.

<footnote>*Department of Computer Science, Université Libre de Bruxelles, Belgium. Email: wcamesva@ulb.ac.be. Supported by the Netherlands Organisation for Scientific Research (NWO), grant no. 613.001.217, and an ARC grant from the Wallonia-Brussels Federation of Belgium.</footnote>

<footnote>†Department of Mathematics, Radboud University Nijmegen, Netherlands. Email: ross.kang@gmail.com. Supported by a Vidi grant (639.032.614) of the Netherlands Organisation for Scientific Research (NWO).</footnote>

<footnote>‡Department of Mathematics, Radboud University Nijmegen, Netherlands and LORIA, Université de Lorraine, Nancy, France. Email: francois.pirot@loria.fr.</footnote>
If true, this bound would be sharp for even $\Delta$, by considering a 5-cycle and substituting each of its vertices with a copy of a stable set of size $\frac{1}{2}\Delta$. Molloy and Reed [9] proved the existence of some absolute constant $\varepsilon > 0$ such that $\chi_2'(G) \le (2-\varepsilon)\Delta^2$ for any graph $G$ with $\Delta_G = \Delta$. Despite significant efforts, cf. e.g. [1], there is no explicit lower bound on $\varepsilon$ greater than 0.001 (though better results hold when $\Delta$ is large).

The problem remains difficult if we restrict to a class defined by some forbidden set of subgraphs, say, cycles. The following conjecture of Faudree, Gyárfás, Schelp and Tuza [5] has also remained wide open since the 1980s.

**Conjecture 2 ([5]).** For a bipartite graph $G$ with $\Delta_G = \Delta$, $\chi_2'(G) \le \Delta^2$.

Balanced complete bipartite graphs meet the conjectured bound. A more general assertion due to Mahdian [8] is also open: perhaps it suffices to forbid just one in particular of the odd cycle lengths rather than all of them.

**Conjecture 3 ([8]).** For a $C_5$-free graph $G$ with $\Delta_G = \Delta$, $\chi_2'(G) \le \Delta^2$.

By contrast, the best understood classes are when the forbidden set includes some bipartite graph. In particular, Mahdian [8] showed the following for $C_4$. This was subsequently extended to a similar statement with $C_4$ replaced by any bipartite $H$ by Vu [11]. See [7] for an explicit derivation with $H = C_{2k}$.

**Theorem 4 ([8]).** Fix $\varepsilon > 0$. If $G$ is a $C_4$-free graph with $\Delta_G = \Delta$, then, provided $\Delta$ is large enough, $\chi_2'(G) \le (2+\varepsilon)\Delta^2/\log\Delta$. This is sharp up to the multiplicative constant factor.

Note that graphs of small maximum degree remain a hypothetical obstruction to the outright confirmation of Conjectures 1 or 2 for $C_4$-free graphs.

Based on the above frustrating state of affairs, it is justified to pursue a simpler parameter than $\chi_2'$, even for restricted graph classes. In particular, a strong clique of $G$ is a set of edges every pair of which are incident or connected by an edge in $G$; the strong clique number $\omega_2'(G)$ of $G$ is the size of a largest such set. No two edges of a strong clique may have the same colour in a strong edge-colouring, so $\omega_2'(G) \le \chi_2'(G)$. Thus the following classic result is viewed as supporting evidence towards Conjecture 2.

**Theorem 5 ([6]).** For a bipartite graph $G$ with $\Delta_G = \Delta$, $\omega_2'(G) \le \Delta^2$.

By forbidding just one fixed odd cycle length rather than all of them, we refine and improve upon Theorem 5 as follows.

**Theorem 6.** Let $G$ be a graph with $\Delta_G = \Delta$.

(i) $\omega_2'(G) \le \frac{5}{4}\Delta^2$ if $G$ is triangle-free.

(ii) $\omega_2'(G) \le \Delta^2$ if $G$ is $C_5$-free.

(iii) $\omega_2'(G) \le \Delta^2$ if $G$ is $C_{2k+1}$-free, $k \ge 3$, provided $\Delta \ge 3k^2 + 10k$.
The blown-up 5-cycles are triangle-free so Theorem 6(i) is best possible when $\Delta$ is even. Parts (ii) and (iii) of Theorem 6 are sharp for the balanced complete bipartite graphs. They are a common strengthening and generalisation of Theorem 5 and a result of Mahdian [8, Thm. 15]. Part (ii) may be viewed as support for Conjecture 3. Parts (i) and (ii) have a common ingredient, but curiously the three proofs for Theorem 6 are all quite distinct.

We naturally find it interesting to also consider forbidden cycle lengths that are even. In this case, we propose the following behaviour.

**Conjecture 7.** For a $C_{2k}$-free graph $G$ with $\Delta_G = \Delta$, $\omega'_2(G) \le (2k-1)(\Delta-k+1)$.

If true, this is sharp (for $\Delta \ge 2k-2$) by considering some clique on $2k-1$ vertices, to each vertex of which is attached $\Delta - 2k + 2$ pendant edges. We refer to this construction as a *hairy clique* of order $2k-1$.

In support of Conjecture 7, we have the following three bounds. The first essentially settles the $k=2$ case. The second is too large by an $O(k)$ factor. The third is almost the conjectured bound, but with the exclusion of two more cycle lengths (also absent in the hairy clique of order $2k-1$).

**Theorem 8.** Let $G$ be a graph with $\Delta_G = \Delta$.

(i) $\omega'_2(G) \le 3(\Delta - 1)$ if $G$ is $C_4$-free, provided $\Delta \ge 4$.

(ii) $\omega'_2(G) \le 10k^2(\Delta - 1)$ if $G$ is $C_{2k}$-free, $k \ge 3$.

(iii) $\omega'_2(G) \le (2k-1)(\Delta-1)+2$ if $G$ is $\{C_{2k}, C_{2k+1}, C_{2k+2}\}$-free, $k \ge 2$.

We invite the reader to notice the qualitative difference between excluding an odd cycle length versus an even one. In the latter case, Theorem 8(ii) and Theorem 4 combine to reveal an asymptotic difference in extremal behaviour between the strong clique number and the strong chromatic index. In the former case, it is conjectured that there is no such difference.

We have delved a little further by considering the effect of forbidden (even) cycles within the class of bipartite graphs. For this specific case, we propose the following.

**Conjecture 9.** For a $C_{2k}$-free bipartite graph $G$ with $\Delta_G = \Delta$, $\omega'_2(G) \le k(\Delta - 1) + 1$.

If true, this is sharp (for $\Delta \ge k-1$) by considering a complete bipartite graph $K_{k-1,\Delta}$ with parts of size $k-1$ and $\Delta$, to one vertex in the part of size $\Delta$ is attached $\Delta - k + 1$ pendant edges. In support of Conjecture 9, we have the following result.

**Theorem 10.** For a $\{C_3, C_5, C_{2k}, C_{2k+2}\}$-free graph $G$ with $\Delta_G = \Delta$, $\omega'_2(G) \le \max\{k\Delta, 2k(k-1)\}$.
This is nearly sharp by the example mentioned just above. A small step in
the proof is a curious property of maximising the strong clique number: if
we are interested in a class of graphs that are {$C_3, C_5$}-free, then we may as
well exclude all other odd cycle lengths at the same time (Lemma 22). This
same reduction easily implies a result intermediary to Theorems 5 and 6(ii).
Let us remark that in general (i.e. without a cycle restriction) the bound

$\omega'_2(G) \le \frac{5}{4}\Delta^2$ remains conjectural. Śleszyńska-Nowak [10] showed a bound
of $\frac{3}{2}\Delta^2$, which was improved to $\frac{4}{3}\Delta^2$ by Faron and Postle [4].

**Notational conventions**

Let $G$ be a graph or multigraph. $V(G)$ denotes its vertex set. $E(G)$ denotes its edge set. $L(G)$ denotes its line graph. We write $|G|$ for $|V(G)|$ and $e(G)$ for $|E(G)| = |L(G)|$.

Given a subset $S \subseteq V(G)$, the sub(multi)graph induced by $S$ is denoted
by $G[S]$. Given disjoint subsets $S_1, S_2 \subseteq V(G)$, the bipartite sub(multi)graph
induced by the edges between $S_1$ and $S_2$ is denoted by $G[S_1 \times S_2]$. We write
$E_G(S_2, S_2)$ for $E(G[S_1 \times S_2])$ and $e_G(S_2, S_2)$ for $e(G[S_1 \times S_2])$. We write
$I_G(S)$ for $E(G[S]) \cup E(G[S \times (V(G) \setminus S)])$, the set of edges incident to $S$.
The neighbourhood $N_G(S)$ of $S$ is the set $\{v' | v \in S, v' \notin S, vv' \in E(G)\}$ of
neighbours of $S$. For a vertex $v \in V(G)$, we write $N_G(v)$ instead of $N_G(\{v\})$.
The closed neighbourhood $N_G[v]$ of $v$ is $\{v\} \cup N_G(v)$. The degree $\deg_G(v)$
of $v$ is $|I_G(\{v\})|$ (and so $\deg_G(v) = |N_G(v)|$ if $G$ is a simple graph). When
the context is clear, we sometimes drop the subscript $G$.

The distance between two vertices is the length of (i.e. the number of
edges in) a shortest path in $G$ that joins them. The distance between two
edges is their distance in $L(G)$. The distance between a vertex and an edge
is the smaller of the distances between the vertex and the endpoints. The
square $G^2$ of $G$ is formed from $G$ by adding an edge for every pair of vertices
that are at distance 2. Note $\omega'_2(G) = \omega(L(G)^2)$ and $\chi'_2(G) = \chi(L(G)^2)$
where $\omega$ denotes the clique number and $\chi$ the chromatic number.

2 No triangles or no 5-cycles

This section is devoted to showing parts (i) and (ii) of Theorem 6. A
common element of the proof is a lemma about the *Ore-degree* $\sigma_G$ of $G$, the
largest over all edges of $G$ of the sum of the two endpoint degrees. The
following generalises a recent result due to Faron and Postle [4].

**Theorem 11.** For a $C_5$-free graph $G$, $\omega'_2(G) \le \frac{1}{4}\sigma_G^2$.

This directly implies Theorem 6(ii) (and hence Theorem 5) because the
sum of two degrees in $G$ is always at most $2\Delta_G$. Theorem 11 follows from a
slightly more technical version. For a sub(multi)graph $H$ of a (multi)graph
$G$, the Ore-degree $\sigma_G(H)$ of $H$ in $G$ is $\max_{xy \in E(H)}(\deg_G(x) + \deg_G(y))$.
**Lemma 12.** If $G$ is a $C_5$-free multigraph and $H$ is a submultigraph of $G$ such that $E(H)$ is a clique in $L(G)^2$, then $e(H) \le \Delta_H(\sigma_G(H) - \Delta_H) \le \frac{1}{4}\sigma_G(H)^2$.

Before proving this, we first show how it yields Theorem 6(i). (In fact, we only need the weaker bipartite version due to Faron and Postle [4].)

*Proof of Theorem 6(i).* Let $G$ be a triangle-free graph with $\Delta_G = \Delta$. Let $H$ be a vertex-minimal subgraph of $G$ whose edges form a maximum clique in $L(G)^2$. Let $v \in V(G)$ be a vertex satisfying $\deg_H(v) = \Delta_H$. From now on we call $H$ and its edges blue. Let $G_T = G[V_T]$ and $H_T = H[V_T]$, where $V_T = V(H) \setminus N_G[v]$.

Let $C_1, C_2, \dots$ denote the connected components of $H_T$ that contain at least one edge. Fix one such component $C_i$ and let $pq$ be an edge in $C_i$. For all $x \in N_H(v)$, the blue edges $xv$ and $pq$ must be within distance 2. They are not incident, so either $xp \in E(G)$ or $xq \in E(G)$, but we cannot have both since $G$ is triangle-free. It follows that $N_H(v)$ can be partitioned into $A_i = N_G(p) \cap N_H(v)$ and $\bar{A}_i = N_G(q) \cap N_H(v)$. We will call $\{A_i, \bar{A}_i\}$ the partition induced by $pq$. Now suppose $C_i$ contains an edge $e$ which is incident to $pq$. Then since $G$ is triangle-free, $e$ and $pq$ must induce the same partition. It follows inductively that all edges in $C_i$ induce the same partition $\{A_i, \bar{A}_i\}$ of $N_H(v)$. Figure 1 illustrates this structure.

Let $C_1, \dots, C_k$ be the components (if they exist) that induce the trivial partition $\{\emptyset, N_H(v)\}$. Let $M = |C_1| + \dots + |C_k|$ denote the number of edges that are in these 'trivial' components. On the other hand, let $G_{\text{bip}} = G[\bigcup_{i \ge k+1} V(C_i)]$ and $H_{\text{bip}} = H[\bigcup_{i \ge k+1} V(C_i)]$ be the graphs induced by the remaining 'nontrivial' components.

**Claim 13.** $M \le (\Delta - \Delta_H)\Delta$.

**Claim 14.** $\sigma_{G_{\text{bip}}}(H_{\text{bip}}) \le 2\Delta - \Delta_H - M/\Delta$.

**Claim 15.** $G_{\text{bip}}$ is bipartite.

Before proving these claims, we show how they imply the theorem. Note that $E(H_{\text{bip}})$ is a clique not only in $L(G)^2$ but also in $L(G_{\text{bip}})^2$. So by Claim 15, we may apply Lemma 12 and then Claim 14, yielding

$$e(H_{\text{bip}}) \le \frac{1}{4}\sigma_{G_{\text{bip}}}(H_{\text{bip}})^2 \le \frac{1}{4}\left(2\Delta - \Delta_H - \frac{M}{\Delta}\right)^2.$$

It follows that $\omega(L(G)^2)$ is at most

$$\begin{align*}
e(H) &= |I_H(N_G(v))| + e(H_T) \le \Delta_H \deg_G(v) + M + e(H_{\text{bip}}) \\
&\le \Delta_H \Delta + M + \frac{1}{4} \left( 2\Delta - \Delta_H - \frac{M}{\Delta} \right)^2 \\
&= \Delta^2 + \frac{1}{4} \left( \Delta_H + \frac{M}{\Delta} \right)^2 \le \frac{5}{4} \Delta^2,
\end{align*}$$
<figure><img src="image_2.png" /><figcaption>Figure 1: The structure described in the proof of Theorem 6(i). Blue edges are in $H$, red edges are in $G$ but not in $H$, and black edges could be either. In this picture, $H_{\text{bip}} \subseteq G_T$ has two (blue) connected components, induced by $X_1 \cup Y_1$ respectively $X_2 \cup Y_2$. The blue neighbourhood $N_H(v)$ is partitioned into two sets $A_1$ (its left two vertices) and $\bar{A}_1$ (the remaining three vertices on the right), such that $X_1$ is complete to $A_1$ and $Y_1$ is complete to $\bar{A}_1$. The neighbourhoods of $X_2$ and $Y_2$ induce another partition of $N_H(v)$. Not all edges are depicted here. In particular, we have left out the (possibly red) edges inside $G_T$ that ensure that all of its blue edges are within distance 2.</figcaption></figure>
where we used Claim 13 in the last line. This concludes the proof, conditioned on Claims 13–15.

Given the $i$th component $C_i$, let $X_i$ respectively $Y_i$ denote the set of vertices in $C_i$ whose neighbourhood in $N_H(v)$ is $A_i$ respectively $\bar{A}_i$. Note that $X_i$ is complete to $A_i$ and $Y_i$ is complete to $\bar{A}_i$. Furthermore, the bipartite subgraph of $H$ induced by $C_i$ has parts $X_i$ and $Y_i$.

*Proof of Claim 13.* If $C_i$ is a trivial component ($1 \le i \le k$) then $Y_i$ is complete to $\bar{A}_i = N_H(v)$. Therefore $|\bigcup_{1 \le i \le k} Y_i| \le \Delta$, and for the same reason all $y \in \bigcup_{1 \le i \le k} Y_i$ satisfy $\deg_{H_T}(y) \le \Delta - \bar{\Delta}_H$. So $M \le \sum_{y \in \bigcup_{1 \le i \le k} Y_i} \deg_{H_T}(y) \le \Delta(\Delta - \bar{\Delta}_H)$. $\diamond$

*Proof of Claim 14.* Let $e = pq \in E(H_{\text{bip}})$. Then for all $x \in N_H(v)$, $x$ must be adjacent to either $p$ or $q$. So there are $\deg_H(v) = \Delta_H$ edges between $\{p, q\}$ and $N_H(v)$. Also, $pq$ must be at distance 2 of each of the $M$ edges induced by the trivial components. So there are at least $M/\Delta$ edges between $\{p, q\}$ and the trivial components. So at least $\Delta_H + M/\Delta$ edges incident to $\{p, q\}$ are not in $G_{\text{bip}}$. It follows that $\sigma_{G_{\text{bip}}}(e) = \deg_{G_{\text{bip}}}(p) + \deg_{G_{\text{bip}}}(q) \le 2\Delta - \bar{\Delta}_H - M/\Delta$. $\diamond$

*Proof of Claim 15.* Suppose there are two different nontrivial components, $C_i$ and $C_j$. We will first show that we may then assume that either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Indeed, if either $\bar{A}_j \subseteq A_i$ or $A_i \subseteq \bar{A}_j$, then after interchanging $X_j$ and $Y_j$ (and thus interchanging $A_j$ and $\bar{A}_j$), we obtain $A_j \subseteq A_i$ or $A_i \subseteq A_j$. So we may assume for a contradiction that none of $A_i \subseteq A_j$, $A_i \subseteq \bar{A}_j$, $A_j \subseteq A_i$, $\bar{A}_j \subseteq A_i$ holds. But then there exist $a \in A_i \cap \bar{A}_j$, $b \in A_i \cap A_j$, $c \in \bar{A}_i \cap A_j$ and $d \in \bar{A}_i \cap \bar{A}_j$. Furthermore, because each component contains at least one blue edge, there are blue edges $(x_i, y_i) \in X_i \times Y_i$ and $(x_j, y_j) \in X_j \times Y_j$ that have to be connected by an edge in order to have them within distance 2. If $x_i x_j$ is an edge, then $x_i x_j b$ forms a triangle. Similarly, if $x_i y_j$, $y_i y_j$ or $x_j y_i$ is an edge then $x_i y_j a$, $y_i y_j d$ or $x_j y_i c$ is a triangle, respectively. Contradiction.

It follows that we can reorder the components by inclusion, so that $A_{k+1} \subseteq A_{k+2} \subseteq \dots$. Now we are ready to show that $G_{\text{bip}}$ is bipartite on parts $X = \bigcup_{i \ge k+1} X_i$ and $Y = \bigcup_{i \ge k+1} Y_i$. Suppose $X$ is not a stable set. Then there are $x_1, x_2 \in X$ that form an edge, where $x_1 \in X_i$ and $x_2 \in X_j$ for some $i \le j$. Since $\emptyset \ne A_i \subseteq A_j$, there must be a triangle in $x_1 x_2 A_i$. Contradiction. Similarly, suppose $Y$ is not a stable set. Then there are $y_1, y_2 \in Y$ that form an edge, where $y_1 \in Y_i$ and $y_2 \in Y_j$ for some $i \le j$. Since $\emptyset \ne \bar{A}_j \subseteq \bar{A}_i$, there must be a triangle in $y_1 y_2 \bar{A}_j$. Contradiction. $\diamond$

This completes the proof of Theorem 6(i). $\square$
*Proof of Lemma 12.* Let $G$ be a $C_5$-free multigraph and $H$ be a submultigraph of $G$ whose edges form a maximum clique in $L(G)^2$. Let $v \in V(G)$ be a vertex satisfying $\deg_H(v) = \Delta_H$.

We may assume that $|N_H(v)| \ge 2$. Indeed if $|N_H(v)| = 1$ then, writing $N_H(v) = \{u\}$, the multiplicity of $uv$ in $H$ is equal to $\Delta_H$. Each vertex in $N_G(\{u, v\})$ is incident to at most $\Delta_H$ edges of $H$, and there are at most $\deg_G(u) + \deg_G(v) - 2\Delta_H \le \sigma_G(H) - 2\Delta_H$ such vertices. Therefore $e(H) \le \Delta_H + (\sigma_G(H) - 2\Delta_H)\Delta_H \le \Delta_H(\sigma_G(H) - \Delta_H)$, as desired.

Now let $E^* \subseteq E(H)$ denote the set of those edges $st \in E(H)$ for which $s, t \notin N_G(v)$. Let $st \in E^*$. Then, for all $u \in N_H(v)$, $vu$ must be within distance 2 of $st$, so either $us \in E(G)$ or $ut \in E(G)$. Without loss of generality, $us \in E(G)$. Because $G$ has no $C_5$ and $|N_H(v)| \ge 2$, it follows that $t$ is anticomplete to $N_H(v) \setminus \{u\}$, so in fact $s$ is complete to $N_H(v)$ and $t$ is anticomplete to $N_H(v)$. We derived this for all $st \in E^*$, so there exists a subset $S \in V(H)$ such that

$$ (i) \ E^* \subseteq I_H(S), \text{ and} $$

$$ (ii) \ S \text{ is complete to } N_H(v). $$

Since each edge of $H$ is either in $E^*$ (and thus has an endpoint in $S$) or has an endpoint in $N_G(v)$, we can cover $E(H)$ with the following subsets:

$$ E_S = I_H(S), \ E_1 = I_H(N_G(v) \setminus N_H(v)), \text{ and } E_2 = I_H(N_H(v)) \setminus E_S. $$

Each vertex is incident to at most $\Delta_H$ edges of $H$, so $|E_S| \le \Delta_H|S|$. Furthermore, $|E_1| \le \Delta_H|N_G(v) \setminus N_H(v)| \le \Delta_H(\deg_G(v) - \Delta_H)$ by our choice of $v$. By property (ii), each vertex $x \in N_H(v)$ is incident to at most $\deg_G(x) - |S|$ edges that are not incident to $S$. Thus, $|E_2| \le \sum_{x \in N_H(v)} (\deg_G(x) - |S|) \le \Delta_H(\sigma_G(H) - \deg_G(v) - |S|)$. In conclusion,

$$ e(H) \le |E_S| + |E_1| + |E_2| \le \Delta_H(\sigma_G(H) - \Delta_H). $$

The last expression is largest if $\Delta_H = \frac{1}{2}\sigma_G(H)$, so $e(H) \le \frac{1}{4}\sigma_G(H)^2$. $\square$

### 3 No $(2k+1)$-cycles or no $2k$-cycles

In this section, we prove Theorem 6(iii) and Theorem 8(ii). The methods are quite different from those of the previous section. In both proofs, we utilise a Turán-type lemma for graphs with no path $P_{2k+1}$ of order $2k+1$.

Given a graph $G$ and a subset $S \subseteq V(G)$, an edge $uv$ out of $S$, with $u \in S$ and $v \notin S$, say, is called *b-branching out of* $S$ if $|N_G(v) \cap S| \ge b$.

**Lemma 16.** Fix $k \ge 2$. Given a graph $G$ and a subset $X \subseteq V(G)$, if $G[X \times (V(G) \setminus X)]$ is $P_{2k+1}$-free, then at most $k^2|X|$ edges are $k$-branching out of $X$.
*Proof.* Let $G$ and $X \subseteq V(G)$ satisfy the hypothesis. Without loss of gener-
ality, we may assume that $G$ is connected. We prove the result by induction
on $|X|$. The statement is trivially true if $|X| < k$. For the induction, let us
assume that $|X| \ge k(\ge 2)$ and that the statement is true for any $X' \subseteq V(G)$
with $|X'| < |X|$.

Suppose there is some $x \in X$ that is incident to at most $k$ edges that are $k$-branching. We then have by induction that there are at most $k^2(|X| - 1)$ edges that are $k$-branching out of $X \setminus \{x\}$. Let us call a vertex $v \notin X$ pivotal if there exists an edge incident to $v$ which is $k$-branching out of $X$ but not $k$-branching out of $X \setminus \{x\}$. Each pivotal vertex must be adjacent to $x$ and must have exactly $k-1$ neighbours in $X \setminus \{x\}$. It follows that there are at most $k$ pivotal vertices, each of which is incident to exactly $k$ edges that are $k$-branching out of $X$ (but not $k$-branching out of $X \setminus \{x\}$). In conclusion, at most $k^2(|X| - 1) + k^2 = k^2|X|$ edges are $k$-branching out of $X$.

There remains the possibility that every vertex of $X$ is incident to at least $k+1$ edges that are $k$-branching. In this case, however, we can construct a path through the following iterative process. Consider an arbitrary $k$-branching edge out of $X$ and let $x_0'$ be its endpoint in $V(G)\setminus X$. Suppose we have constructed a path $x_0'x_0\cdots x_{i-1}'x_{i-1}x_i'$ for some $i \ge 0$, such that $x_i'$ is incident to an edge which is $k$-branching out of $X$. Note that $x_i'$ has at least $k$ neighbours in $X$ by definition. If $i < k$, we may choose $x_i \in X \setminus \{x_0, \dots, x_{i-1}\}$. Subsequently, we may choose a $k$-branching edge $x_i x_{i+1}'$ such that $x_{i+1}' \in V(G) \setminus (X \cup \{x_0', \dots, x_i'\})$. This process certifies that $x_0'x_0\cdots x_k'$ is in $G[X \times (V(G) \setminus X)]$. This path is of order $2k+1$, contrary to our assumption. $\square$

In addition to Lemma 16, we need a basic bound on the Turán number
of a path $P_{\ell+1}$ of order $\ell+1$ due to Erdős and Gallai [3].

**Lemma 17 ([3]).** For a $P_{\ell+1}$-free graph $G$, $e(G) \le (\ell-1)|G|/2$.

*Proof of Theorem 6(iii).* Let $G$ be a $C_{2k+1}$-free graph with $\Delta_G = \Delta \ge 16k$. Let $H$ be a subgraph of $G$ whose edges form a maximum clique in $L(G)^2$. Thus bounding $\omega(L(G)^2)$ is equivalent to bounding $e(H)$. Let $v \in V(G)$ be a vertex satisfying $\deg_H(v) = \Delta_H$. For short, we write $A_v = N_G(v)$ and $B_v = N_G(N_G[v])$. Note that if $E(H[B_v]) = \emptyset$, then every edge in $H$ is incident to $A_v$, and $e(H) \le \deg_G(v)\Delta \le \Delta^2$.

For any edge $xy \in E(H[B_v])$, it must hold that $N_H(v) \subseteq N_G(\{x, y\})$. If, for every such edge, it holds that $N_G(x) \cap N_H(v) = \emptyset$, say, (and so $N_H(v) \subseteq N_G(y)$), then $e(H) \le \deg_G(v)\Delta_H + \Delta(\Delta - \Delta_H) \le \Delta^2$.

Fix $xy \in E(H[B_v])$ such that $N_G(x) \cap N_H(v) \neq \emptyset$ and $N_G(y) \cap N_H(v) \neq \emptyset$. Let $\{X, Y\}$ be a non-trivial partition of $N_H(v)$ such that $X \subseteq N_G(x)$ and $Y \subseteq N_G(y)$. We will need the following claim.

**Claim 18.** (i) $G[A_v]$ is $P_{2k}$-free.
(ii) $G[X \times (B_v \setminus \{x, y\})]$ and $G[Y \times (B_v \setminus \{x, y\})]$ are $P_{2k-1}$-free.

*Proof.* (i) If $G[A_v]$ contains a path $P$ of order $2k$, then the concatenation of $P$ with $v$ is a cycle of order $2k+1$ in $G$, a contradiction.

(ii) If $G[X \times (B_v \setminus \{x, y\})]$ (say) contains a path of order $2k-1$, then there must be a subpath $P$ of order $2k-3$ such that both its endpoints are in $X$. Now for any $b \in Y$, the concatenation of $P$ with the path $vbyx$ is a cycle of length $2k+1$ in $G$, a contradiction. $\square$

Letting $C$ denote the set of $(2k-3)$-branching edges out of $N_H(v)$ with respect to the graph $G[N_H(v) \times (B_v \setminus \{x, y\})]$, note that the edges of $H$ can be covered by the following six sets:

$$ I_H(\{v, x, y\}), \quad I_H(N_G(v) \setminus N_H(v)), \quad E(H[A_v]), \\ C, \quad E_H(N_H(v), B_v \setminus \{x, y\}) \setminus C, \quad E(H[B_v \setminus \{x, y\}]). $$

We have $|I_H(\{v, x, y\})| \le 3\Delta_H - 1$ and $|I_H(N_G(v) \setminus N_H(v))| \le (\Delta - \Delta_H)\Delta_H$. Also, $e(H[A_v]) \le (k-1)\Delta$ by Lemma 17 and Claim 18(i).

Let $C_x$ (resp. $C_y$) be the set of $(k-1)$-branching edges out of $X$ (resp. $Y$) with respect to the graph $G[X \times (B_v \setminus \{x, y\})]$ (resp. $G[Y \times (B_v \setminus \{x, y\})]$). By Lemma 16 and Claim 18(ii), $|C_x| \le (k-1)^2|X|$ and $|C_y| \le (k-1)^2|Y|$. By the pigeonhole principle, for every set of edges of $C$ incident to a single vertex in $B_v \setminus \{x, y\}$, more than half of them belong to $C_x$ or to $C_y$. Thus $|C| \le 2((k-1)^2|X|+(k-1)^2|Y|) = 2(k-1)^2\Delta_H$. We next bound $|E_H(N_H(v), B_v \setminus \{x, y\}) \setminus C|$.

Supposing that there are edges in $E_H(N_H(v), B_v \setminus \{x, y\}) \setminus C$, let $A'$ be the set of vertices in $N_H(v)$ that are incident to such an edge and let $u \in A'$ be a vertex of minimum degree in $H[A']$. Note that $\deg_{H[A']}(u) \le 2(k-1)$ by Lemma 17 and Claim 18(i). Let $uw \in E_H(N_H(v), B_v \setminus \{x, y\})$ be an edge that is not $(2k-3)$-branching out of $N_H(v)$. By crudely bounding the number of edges that are within distance 2 of $uw$ and not $(2k-3)$-branching, we have that

$$ \begin{aligned} & |E_H(N_H(v), B_v \setminus \{x, y\}) \setminus C| \\ & \le |N_G(u) \cap (B_v \setminus \{x, y\})| \cdot (2k-4) + |N_G(w) \cap (B_v \setminus \{x, y\})| \cdot (2k-4) \\ & \quad + |N_G(u) \cap A'| \cdot \Delta + (|N_G(w) \cap A'| - 1) \cdot \Delta \\ & \le \Delta(2k-4) + \Delta(2k-4) + 2(k-1)\Delta + (2k-5)\Delta \\ & = (8k-15)\Delta. \end{aligned} $$

It only remains to bound the number of edges of $H[B_v \setminus \{x, y\}]$. First observe that we may assume $\deg_H(v) = \Delta_H \ge 4k-6$, for otherwise $e(H) \le |N_H[\{u, w\}]|\Delta_H < 2(4k-6)\Delta$ (which is at most $\Delta^2$ if $\Delta \ge 16k$). Let $x'y'$ be an edge of $H[B_v \setminus \{x, y\}]$. Write $d_{x'}$ for $|N_G(x') \cap N_H(v)|$ and $d_{y'}$ for $|N_G(y') \cap N_H(v)|$. As we have already observed earlier, $N_G(\{x', y'\}) \supseteq$
$N_H(v)$, and so $d_{x'} + d_{y'} \ge \Delta_H$. If both $d_{x'} \ge 2k-3$ and $d_{y'} \ge 2k-3$, then the number of edges of $C$ incident to $\{x', y'\}$ is at least $d_{x'} + d_{y'} \ge \Delta_H$, and so one of $x'$ or $y'$, say $y'$, is incident to at least $\Delta_H/2$ edges of $C$. Otherwise, $d_{x'} \le 2k-4$ (say) and so $d_{y'} \ge \Delta_H - 2k + 4 \ge \Delta_H/2$, in which case $y'$ is incident to at least $\Delta_H/2$ edges of $C$. In either case, the number of edges of $H[B_v \setminus \{x, y\}]$ incident to $y'$ is at most $\Delta - \Delta_H/2$. Since $x'y'$ was arbitrary, what we have shown is that $H[B_v \setminus \{x, y\}]$ admits a vertex cover each member of which is incident to at least $\Delta_H/2$ edges of $C$ and to at most $\Delta - \Delta_H/2$ edges of $H[B_v \setminus \{x, y\}]$. The size of this vertex cover is at most $|C|$ divided by $\Delta_H/2$. It then follows, using our earlier derived bound on $|C|$, that

$$e(H[B_v \setminus \{x, y\}]) \le \frac{2(k-1)\Delta_H}{\Delta_H/2} (\Delta - \Delta_H/2) \\ = 2(k-1)(2\Delta - \Delta_H).$$

Summing all of the above estimates, we deduce that the number of edges in $H$ is at most

$$3\Delta_H - 1 + (\Delta - \Delta_H)\Delta_H + (k-1)\Delta \\ + 2(k-1)^2\Delta_H + (8k-15)\Delta + 2(k-1)(2\Delta - \Delta_H) \\ \le \frac{1}{4}\Delta^2 + (2k^2 + 7k - 13)\Delta,$$

which is at most $\Delta^2$ if $\Delta \ge 3k^2 + 10k$. $\square$

<figure><img src="image_3.png" /></figure>

*Proof of Theorem 8(ii).* Let $G$ be a $C_{2k}$-free graph with $\Delta_G = \Delta$. Let $H$ be a subgraph of $G$ whose edges form a maximum clique in $L(G)^2$. Choose an edge $uv \in E(H)$, and define $A_u = N_G(u) \setminus \{v\}$ and $A_v = N_G(v) \setminus N_G[u]$. For short we will write $A = A_u \cup A_v$ for the neighbourhood of $\{u, v\}$ and we also need the second-order neighbourhood $B = N_G(A) \setminus (A \cup \{u, v\})$. Note that $|A| \le 2\Delta - 2$.

Letting $C$ denote the set of $(2k-1)$-branching edges out of $A \cup \{u, v\}$, note that the edges of $H$ can be covered by the following four sets:

$$I_H(\{u, v\}), E(H[A]), C, E_H(A, B) \setminus C.$$

**Claim 19.** (i) $G[A]$ is $P_{2k-1}$-free.

(ii) $G[A_u \times B]$ and $G[A_v \times B]$ are $P_{2k+1}$-free.

*Proof.* (i) Suppose that there is a path $x_0 \cdots x_{2k-2}$ of order $2k-1$ in $G[A_u \cup A_v]$. Without loss of generality assume that $x_0 \in A_u$. Then $x_{2k-3} \notin A_v$ or else $ux_0 \cdots x_{2k-3}v$ would be a cycle of length $2k$ in $G$, a contradiction. So $x_{2k-3} \in A_u$. Also $x_{2k-2} \in A_v$ or else $ux_0 \cdots x_{2k-2}$ would be a cycle of length $2k$. Then $x_1 \in A_v$ or else $ux_1 \cdots x_{2k-2}v$ would be a cycle of length
2k. Now take the least i such that $x_{2i-1} \in A_v$ and $x_{2i+1} \in A_u$. Since $x_1 \in A_v$ and $x_{2k-3} \in A_u$, such an $i \in [2k-2]$ exists. But this implies that $ux_0 \cdots x_{2i-1}vx_{2k-2} \cdots x_{2i+1}$ is a cycle of length 2k, a contradiction.

(ii) In any path of order $2k+1$ in $G[A_u \times B]$, say, there is a path of order $2k-1$ with both of its endpoints in $A_u$. This path together with $u$ forms a $C_{2k}$ in $G$, a contradiction. $\diamond$

Note that $|I_H(\{u, v\})| \le 2\Delta - 1$. By Lemma 17 and Claim 19(i), $e(H[A]) \le (k-1)|A|$. Let $C_u$ (resp. $C_v$) be the set of k-branching edges out of $A_u \cup \{u\}$ (resp. $A_v \cup \{v\}$) with respect to the graph $G[A_u \cup V(G) \setminus (A_v \cup \{v\})]$ (resp. $G[A_v \cup V(G) \setminus (A_u \cup \{u\})]$). By Lemma 16 and Claim 19(ii), $|C_u| \le k^2|A_u|$ and $|C_v| \le k^2|A_v|$. By the pigeonhole principle, for every set of edges of $C$ incident to a single vertex in $B$, more than half of them belong to $C_u$ or to $C_v$. Thus $|C| \le 2(k^2|A_u| + k^2|A_v|) = 2k^2|A|$. It remains to bound $|E_H(A, B) \setminus C|$.

Assuming that $E_H(A, B) \setminus C \ne \emptyset$, let $A' \subseteq A$ be the set of those vertices in $A$ that are incident to some edge of $E_H(A, B) \setminus C$ and let $x \in A'$ be a vertex of minimum degree in $H[A']$. Note that $\deg_{H[A']}(x) \le 2k-3$ by Lemma 17 and Claim 19(i). Let $xy \in E(H)$ be an edge that is not $(2k-1)$-branching out of $A \cup \{u, v\}$. By crudely bounding the number of edges that are within distance 2 of $xy$ and not $(2k-1)$-branching, we have that

$$ 
\begin{aligned}
|E_H(A, B) \setminus C| &\le |N_G(x) \cap B| \cdot (2k-2) + |N_G(y) \cap B| \cdot (2k-2) \\
&\quad + |N_G(x) \cap A'| \cdot \Delta + (|N_G(y) \cap A'| - 1) \cdot \Delta \\
&\le \Delta(2k-2) + \Delta(2k-2) + (2k-3)\Delta + (2k-3)\Delta \\
&= (8k-10)\Delta.
\end{aligned}
$$

Combined with the previous estimates and using that $\Delta \ge 3$ (otherwise $G$ is a collection of vertex-disjoint trees and cycles, so the theorem follows straightforwardly), we obtain

$$ 
\begin{aligned}
e(H) &\le 2\Delta - 1 + (2k^2 + k - 1)|A| + (8k - 10)\Delta \\
&\le (4k^2 + 10k - 10)\Delta + 1 - 2k - 2k^2 \le (5k^2 + 14k)(\Delta - 1). \quad \square
\end{aligned}
$$

# 4 No three consecutive cycle lengths

In this section, we prove a stronger version of Theorem 8(iii).

**Theorem 20.** Let $G$ be a graph with $\Delta_G = \Delta$.

(i) $\omega(L(G)^2) \le (\kappa - 2)(\Delta - 1) + 2$ if $G$ is $P_{\kappa+1}$-free, $\kappa \ge 3$.

(ii) $\omega(L(G)^2) \le (\ell - 2)(\Delta - 1) + 2$ if $G$ is $\{C_{\ell-1}, C_\ell, C_{\ell+1}\}$-free, $\ell \ge 5$.
*Proof of Theorem 20.* If $\Delta = 1$ then $\omega(L(G)^2) = 1$. If $\Delta = 2$, then $G$ is a path or a cycle, or a vertex-disjoint union of such graphs. For all such graphs, $\omega(L(G)^2) \le 5 \le (\ell-2)(\Delta-1)+2$. Furthermore, if $G$ is not a 4-cycle or 5-cycle then $\omega(L(G)^2) \le 3$, so $\omega(L(G)^2) \le (\kappa-2)(\Delta-1)+2$. Thus we may assume from now on that $\Delta \ge 3$. The idea of the proof is to assume that $\omega(L(G)^2)$ is large and then iteratively construct a path of order $l+1$ (respectively $k+1$) whose extremal edges are in $E(H)$. This will imply the existence of a cycle (respectively path) of forbidden length; contradiction.

Let $H$ be a subgraph of $G$ whose edges form a maximum clique in $L(G)^2$. Note that $e(H) = \omega(L(G)^2) > \Delta$, for otherwise the conclusion of the theorem is already satisfied. It follows that $G$ contains a path $P_4 = x_1y_1x_2y_2$ that starts and ends on edges $x_1y_1, x_2y_2$ from $E(H)$. Indeed, let $e_1$ and $e_2$ be edges of $E(H)$. If they are not incident to each other, then there must be an edge between them and we have obtained the desired $P_4$. So we may assume that all edges of $E(H)$ are pairwise incident and in particular we can write $e_1 = xy$ and $e_2 = yz$. At most $\Delta$ edges meet in $y$, so $E(H)$ contains an edge $e_3$ that is not incident to $y$ and therefore $e_3$ is incident to $x$. If $e_3 = xq \ne xz$ then $qxyz$ forms the desired $P_4$. Otherwise $xyz$ forms a triangle of edges from $E(H)$. Since $e(H) \ge \Delta + 1 \ge 4$, there is a fourth edge in $E(H)$ incident to the triangle, again yielding a $P_4$.

We now define the paths $W_1 := y_1x_2$ and $W_1^* := x_1y_1x_2y_2$, the latter being the $P_4$ whose existence we derived above. These paths serve as the initialisation step of a construction (described below). The input of this construction is given by a path $W_i := y_1x_2y_2 \dots y_{i-1}x_i$ and a 'preliminary' path $W_i^* := x_1W_iy_i$, with the property that the first and final edge of $W_i^*$ are in $E(H)$. The output consists of longer paths $W_{i+1}$ and $W_{i+1}^*$, with the same properties. For this construction to work, we need the edge set $F_i := E(H) \setminus (I_H(W_i) \cup \{x_1y_i\})$ to be nonempty.

As long as $F_i$ is nonempty, we iterate the following case consideration.

**Case 1.** $F_i$ contains an edge which is incident to the first vertex $x_1$ or the last vertex $y_i$ of $W_i^*$.

Choose such an edge $e_{i+1} \in F_i$ and assume without loss of generality that it is incident to $y_i$. Then we add $e_{i+1}$ to our preliminary path, and we set $W_{i+1}^* = W_i e_{i+1}$ and $W_{i+1} = W_i^*$. By the definition of $F_i$, $y_i$ is the only vertex in $W_i^*$ that is incident to $e_{i+1}$, so $W_{i+1}^*$ is a path as well.

**Case 2.** *Case 1 does not apply.*

Then $F_i$ contains an edge $x_{i+1}y_{i+1}$ which is not incident to $x_1$ or $y_i$. By the definition of $F_i$, $x_{i+1}y_{i+1}$ is not incident to $x_i$ either. Therefore there must be an edge $e^*$ between $x_{i+1}y_{i+1}$ and $x_iy_i$. Without loss of generality, $e^*$ is incident to $x_{i+1}$, so we have $x_i x_{i+1} \in E(G)$ or $y_i x_{i+1} \in E(G)$.

**Subcase 2.1.** $x_i x_{i+1} \in E(G)$.

Then we set $W_{i+1}^* = W_i x_{i+1} y_{i+1}$ and $W_{i+1} = W_i x_{i+1}$.

**Subcase 2.2.** $y_i x_{i+1} \in E(G)$ and subcase 2.1 does not apply.
Then we set $W_{i+1}^* = W_i y_i x_{i+1} y_{i+1} = W_i^* x_{i+1} y_{i+1}$ and $W_{i+1} = W_i y_i x_{i+1}$.

After the final iteration $I$, the set $F_I$ is empty. Since $F_I = E(H) \setminus (I_H(W_I) \cup \{x_1 y_I\})$ and because the number of edges incident to $W_I$ is at most $(\Delta - 1)|W_I| + 1$, it follows that $0 = |F_I| \ge e(H) - 2 - (\Delta - 1)|W_I|$.

Because $G$ is $P_{\kappa+1}$-free, our constructed path $W_I^*$ cannot be too large. More precisely, we must have $\kappa \ge |W_I^*| = |W_I| + 2$, and therefore

$$ \omega(L(G)^2) = e(H) \le (\Delta - 1)|W_I| + 2 \le (\Delta - 1)(\kappa - 2) + 2. $$

This concludes the proof of (i). For (ii), we extend the argument slightly. Suppose for a contradiction that $\omega(L(G)^2) = e(H) \ge (\ell - 2)(\Delta - 1) + 3$. Then $W_I^*$ is a path on $|W_I| + 2 \ge \frac{e(H)-2}{\Delta-1} + 2 \ge \ell + \frac{1}{\Delta-1}$ vertices. Note that in the $i$th iteration, the order of the path $W_I^*$ is increased by either 1 or 2.<fnref n="1" /> Therefore there exists a $j \le I$ such that $|W_j^*| \in \{\ell, \ell+1\}$.

From now on, let us call the edges of $E(H)$ blue and the other edges of $E(G)$ red. First we derive that it suffices to show the existence of a $P_{\ell+1}$ that starts and ends on blue edges. Suppose $G$ has a path $A$ of order $\ell + 1 \ge 6$ that starts with a blue edge $a_1 a_2$ and ends on another blue edge $a_\ell a_{\ell+1}$. These (nonincident) blue edges must be within distance 2, so there must be an edge between them that is not part of $A$. If $a_1 a_{\ell+1} \in E(G)$, then $a_1 a_2 \dots a_{\ell+1}$ is a $C_{\ell+1}$. Similarly, if $a_1 a_\ell \in E(G)$ or $a_2 a_{\ell+1} \in E(G)$, then there is a $C_\ell$. Finally, if $a_2 a_\ell \in E(G)$, then there is a $C_{\ell-1}$. So $G$ contains a cycle of order $\ell - 1$, $\ell$ or $\ell + 1$; contradiction.

So we may assume that $|W_j^*| = \ell$ and $|W_{j+1}^*| = \ell + 2$. To finish the proof, we will derive that $G$ then contains another path of order $\ell + 1$, starting and ending on blue edges.

Write $W_j^* = w_1 \dots w_\ell$. First, since $|W_{j+1}^*| - |W_j^*| = 2$, we must have that $W_{j+1}^* = W_j^* w_{\ell+1} w_{\ell+2}$, where $w_\ell w_{\ell+1}$ is a red edge and $w_{\ell+1} w_{\ell+2}$ is blue. Second, since $w_1 w_2$ and $w_{\ell+1} w_{\ell+2}$ are at distance 2, there is an edge $e^*$ between them. From this observation, we obtain the desired $P_{\ell+1}$ unless $e^* = w_1 w_{\ell+2}$. Third, $w_1 w_2$ and $w_{\ell-1} w_\ell$ must be at distance 2 from each other, so they are connected by an edge $e^{**}$ that is not part of $W_j^*$. This yields a forbidden $C_\ell$ or $C_{\ell-1}$, unless $e^{**} = w_2 w_{\ell-1}$. Fourth, note that $w_{\ell-2} w_{\ell-1}$ is red, for otherwise $w_{\ell+1} w_{\ell+2} w_1 w_2 \dots w_{\ell-2} w_{\ell-1}$ would yield the desired $P_{\ell+1}$.

In summary, we have obtained the cycle $\Gamma = w_{1+1} \dots w_{\ell+2}$, where $w_1 w_2$, $w_{\ell-1} w_\ell$ and $w_{\ell+1} w_{\ell+2}$ are blue, and $w_{\ell-2} w_{\ell-1}$ is red. Furthermore, it holds that $w_2 w_{\ell-1} \in E(G)$.

Next, we are going to focus on the edge $e^{***} = w_{\ell-3} w_{\ell-2}$. Since $\ell \ge 5$, this edge is different from the first edge $w_1 w_2$. Suppose that $e^{***}$ is blue.

Then $w_{\ell-2} w_{\ell-3} \dots w_2 w_{\ell-1} w_\ell w_{\ell+1} w_{\ell+2}$ forms a $P_{\ell+1}$ starting and ending on blue edges. Suppose on the other hand that $e^{***}$ is red. Because $e^{***}$

<footnote n="1">¹$|W_{i+1}^*| - |W_i^*|$ is equal to one in case 1 and subcase 2.1, and equal to two in subcase 2.2.</footnote>
and $w_{\ell-2}w_{\ell-1}$ are consecutive red edges of $W_{j+1}^*$, it follows from the construction of the paths $(W_i^*)_{1\le i\le j+1}$ that there must be a pendant blue edge $w_{\ell-2}w_p$ that is only incident to $\Gamma$ in the vertex $w_{\ell-2}$. (This pendant edge used to be the blue end-edge of some preliminary path $W_i^*$, $i < j$.) Now $w_p w_{\ell-2} w_{\ell-3} \dots w_2 w_1 w_{\ell+2} w_{\ell+1}$ forms a $P_{\ell+1}$, starting and ending on blue edges. $\square$

# 5 No 4-cycles

In this section we prove Theorem 8(i). We proceed by a case analysis. In Subsubcases 2.1.2 and 2.2.1 and Subsubcase 2.2.2.2 we can reduce to the case of the neighbourhood of a triangle, which constitutes exactly the extremal hairy triangle. In the other situations, we derive bounds that are smaller, at most $2\Delta$ in particular.

*Proof of Theorem 8(i).* Let $G$ be a $C_4$-free graph with $\Delta_G = \Delta \ge 4$. Let $H$ be a blue subgraph of $G$ whose edges form a maximum clique in $L(G)^2$. Thus bounding $\omega(L(G)^2)$ is equivalent to bounding $e(H)$. Choose an edge $uv \in E(H)$, and define $A_u = N_G(u) \setminus \{v\}$ and $A_v = N_G(v) \setminus N_G[u]$. For short we will write $A = A_u \cup A_v$ for the neighbourhood of $\{u, v\}$ and we also need the second-order neighbourhood $B = N_G(A) \setminus (A \cup \{u, v\})$.

Note that the edges of $H$ can be partitioned into the following six sets:

$$E_H(\{u\}, A), E_H(\{v\}, A), E_H(A_u, B), E_H(A_v, B), E_H[A]), \{uv\}.$$

We will use the following claim a few times.

**Claim 21.** $e(H[A]) \le 1$.

*Proof.* If not, then $G[A]$ must contain a path of order three, which forms a $C_4$ with $u$ and/or $v$. $\diamond$

We now start the case analysis.

**Case 1.** *No vertex in A has two blue neighbours in B.*

The first thing to notice is that $A_u$ and $A_v$ each contain at most three vertices with a blue edge to $B$. Indeed, if there are four such vertices $x_1, \dots, x_4$ with blue neighbours $y_1, \dots, y_4 \in B$ respectively, then the $(y_i)_{1\le i\le 4}$ must be pairwise distinct to prevent a $C_4$. Therefore the blue edges $(x_i y_i)_{1\le i\le 4}$ are pairwise at distance exactly 2. There can be at most two edges in $G[\{x_1, x_2, x_3, x_4\}]$ and these must be nonincident, for otherwise they form a $C_4$ with $v$. Say these edges are $x_1 x_2$ and $x_3 x_4$ (or a subset thereof). Then $y_1 y_2 y_2 y_4$ is a $C_4$, contradiction. Second, it cannot be that both $e_H(\{v\}, A) \ge 2$ and $e_H(A_u, B) \ge 2$. Indeed, otherwise there are two vertices in $N_H(v)$ that must be complete to two vertices in $B \cap N_H(A_u)$, thus forming a $C_4$, contradiction. So $e_H(\{v\}, A) + e_H(A_u, B) \le \Delta$ (where here we also used our
assumption that $\Delta \ge 4$). And similarly $e_H(\{u\}, A) + e_H(A_v, B) \le \Delta$. It follows that $e(H)$ is at most

$$e_H(\{v\}, A) + e_H(A_u, B) + e_H(\{u\}, A) + e_H(A_v, B) + e(H[A]) + |\{uv\}| \\ \le \Delta + \Delta + 1 + 1 = 2\Delta + 2. \qquad (1)$$

This is bounded from above by $3(\Delta - 1)$ if $\Delta \ge 5$. To conclude the same for the case $\Delta = 4$, we need to reduce the bound in equation (1) by 1.

If $e(H[A]) = 0$, then we get the desired improvement for free. If, on the other hand, $E(H[A])$ is nonempty, then its unique edge $ab$ has both endpoints in either $N(u) \setminus N(v)$ or in $N(v) \setminus N(u)$, (otherwise $abuv$ would form a $C_4$). Without loss of generality, assume $ab$ is induced by $N(u) \setminus N(v)$. In that case it follows that $E_H(\{v\}, A) = \emptyset$ (or otherwise a blue neighbour of $v$ in $A$ would have to be adjacent to $a$ or $b$, forming a $C_4$.)

But then $e_H(\{v\}, A) + e_H(A_u, B) \le 0 + \Delta - 1$, so we have again reduced the upper bound in (1) by 1, as desired.

**Case 2.** At least one vertex in $A$ has two blue edges to $B$.

Without loss of generality, let $x \in A_u$ be such a vertex and let $x_1^*, x_2^*$ denote two of its blue neighbours in $B$.

**Subcase 2.1.** $x$ is the only vertex in $A_u$ that has a blue edge to $B$.

**Subsubcase 2.1.1.** $vx \notin E(G)$.

Suppose there exists $vy \in E_H(\{v\}, A_v)$. Then $y \ne x$ because $vx \notin E(G)$. Also, $yx \notin E(G)$ because otherwise $uvyx$ would be a $C_4$. So $y$ must be adjacent to the two blue neighbours $x_1^*, x_2^*$ of $x$ in $B$, in order to have $vy$ within distance 2 of $xx_1^*$ and $xx_2^*$. But then $xx_1^*x_2^*y$ forms a $C_4$. We deduce

$$E_H(\{v\}, A_v) = \emptyset. \qquad (2)$$

We now show that it is impossible for both $e_H(\{u\}, A_u) \ge 2$ and $e_H(A_v, B) \ge 1$ to hold. Indeed, suppose there are $x_1, x_2 \in E_H(\{u\}, A_u)$ and a blue neighbour $y^* \in B$ of some $y \in A_v$. Since $uy, uy^*, x_1y, x_2y \notin E(G)$ while $yy^*$ must be within distance 2 of both $ux_2$ and $ux_1$, it follows that $y^*x_1, y^*x_2 \in E(G)$, yielding the 4-cycle $ux_1x_2y^*$. Contradiction.

If $e_H(A_v, B) = 0$ then $e(H) \le |N_H(u) \cup N_H(x)| + e(H[A]) \le (2\Delta - 1) + 1 \le 3(\Delta - 1)$, as desired. So we may from now on assume that

$$e_H(\{u\}, A_u) \le 1. \qquad (3)$$

Next, we want to show that $e_H(A_v, B) \le 4$. Suppose for a contradiction that $e_H(A_v, B) \ge 5$.

Suppose first that there exists $y \in A_v$ with (at least) three blue neighbours $y_1^*, y_2^*, y_3^*$ in $B$. Recall that $x_1^*, x_2^* \in B$ are two blue neighbours of $x$. Since $\{x_1^*, x_2^*\}$ has at most one element in common with $\{y_1^*, y_2^*, y_3^*\}$ (otherwise there is a $C_4$) we may without loss of generality assume that
$\{x_1^*, x_2^*\} \cap \{y_1^*, y_2^*\} = \emptyset$. If $xy_1^*, xy_2^*, yx_1^*, yx_2^* \notin E(G)$, then $\{x_1^*, x_2^*\}$ must be complete to $\{y_1^*, y_2^*\}$, yielding a $C_4$. So without loss of generality $xy_1^* \in E(G)$. This implies $xy_2^*, yx_1^*, yx_2^* \notin E(G)$ (otherwise there is a $C_4$ containing $x$ and $y$). So in order to have $yy_2^*$ within distance 2 of $xx_1^*$ and $xx_2^*$, we must have $x_1^*y_2^*, x_2^*y_2^* \in E(G)$, yielding $xx_1^*y_2^*x_2^*$ as a $C_4$. Contradiction. So we have derived that each $y \in A_v$ has at most two blue neighbours in $B$.

Now suppose that some vertex $y_{12} \in A_v$ has two blue neighbours $y_1^*, y_2^*$ in $B$. By the argument in the previous paragraph, it may not be that $|\{x_1^*, x_2^*\} \cap \{y_1^*, y_2^*\}| \in \{0, 2\}$, so without loss of generality $x_2^* = y_2^*$.

Additionally suppose there is another vertex $y_{34} \in A_v$ with two blue neighbours $y_3^*, y_4^*$ in $B$. By the same argument, one of $\{y_3^*, y_4^*\}$ is equal to one of $\{x_1^*, x_2^*\}$. But $x_2^* = y_2^* \notin \{y_3^*, y_4^*\}$ (otherwise there is a $C_4$ containing $y_2^*$ and $v$), so without loss of generality $y_4^* = x_1^*$. Since we assumed that $e_H(A_v, B) \ge 5$, there is yet another vertex $y_5 \in A_v$ with (at least) one neighbour $y_5^* \in B$. Since $y_5y_5^*$ must be within distance 2 of $xx_1^*$ and $xx_2^*$ it follows that $xy_5^* \in E(G)$. Since $G[A]$ does not contain a path of order 3 (otherwise there is a $C_4$), at least one of $y_5y_{12}, y_5y_{34}$ is not an edge. Without loss of generality, $y_5y_{12} \notin E(G)$. Then, in order to have $y_5y_5^*$ within distance 2 of $y_{12}y_2^*$ and $y_{12}y_1^*$, we must either have $y_5^*y_{12} \in E(G)$ (in which case $y_5^*xy_2^*y_{12}$ is a $C_4$) or $y_5^*y_1^*, y_5^*y_2^* \in E(G)$ (in which case $y_5^*y_1^*y_{12}y_2^*$ is a $C_4$). Contradiction.

Thus we have derived that $y_{12}$ is the only vertex in $A_v$ with two blue neighbours in $B$ (namely $y_1^*$ and $y_2^*$). Since we assumed $e_H(A_v, B) \ge 5$, there are three other vertices $y_3, y_4, y_5 \in A_v$ with unique blue neighbours $y_3^*, y_4^*, y_5^* \in B$, respectively. Since $G[A]$ does not contain a path of order 3, the complement of the graph induced by $Y = \{y_{12}, y_3, y_4, y_5\}$ contains a $C_4$. This implies there is a $C_4$ in the graph induced by $\{y_1^*, y_2^*, y_3^*, y_4^*, y_5^*\}$, the set of blue neighbours of $Y$ in $B$. Contradiction.

Thus, we have derived that no vertex in $A_v$ has more than one blue neighbour in $B$. Now let $y_1, \dots, y_5 \in A_v$ be vertices with respective unique blue neighbours $y_1^*, \dots, y_5^* \in B$. Since $G[A]$ does not contain a path of order 3, the complement of the graph induced by $\{y_1, y_2, y_3, y_4, y_5\}$ contains a $C_4$. This implies there is a $C_4$ in the graph induced by $\{y_1^*, y_2^*, y_3^*, y_4^*, y_5^*\}$. Contradiction.

This concludes our proof that $e_H(A_v, B) \le 4$. Then together with (2) and (3), it follows that

$$e(H) \le e_H(\{u\}, A_u) + |\{uv\}| + e_H(\{x\}, B) + e_H(A_v, B) + e(H[A]) \\ \le 1 + 1 + (\Delta - 1) + 4 = \Delta + 5 \le 3(\Delta - 1).$$

**Subsubcase 2.1.2.** $vx \in E(G)$.

Suppose there exists an edge $yy^* \in E_H(A_v, B)$, with $y \in A_v$. Then the absence of 4-cycles dictates that $y$ is not adjacent to $x$ nor to any of its blue neighbours in $B$. Therefore $y^*$ is adjacent to all blue neighbours
of $x$ in $B$, of which there are at least two by assumption. But then these neighbours form a $C_4$ with $x$ and $y^*$. Contradiction. So $E_H(A_v, B) = \emptyset$ and therefore all edges of $H$ are incident to the triangle $uxv$. So $e(H) = e(G[N_H(u) \cup N_H(x) \cup N_H(v)]) \le 3(\Delta - 1)$.

**Subcase 2.2.** There is another vertex $x_2$ in $A_u$ that has a blue edge to $B$.

Note that in this case $x x_2 \in E(G)$, for otherwise there would be a $C_4$ in the graph induced by $u, x, x_2$ and the blue neighbours of $x$ and $x_2$ in $B$. Note furthermore that there cannot be a third vertex $x_3 \in A_u$ that has a blue edge to $B$, for otherwise the same argument yields $x x_3 \in E(G)$ so that $x_2 x x_3 u$ would yield a $C_4$.

**Subsubcase 2.2.1.** $vx \notin E(G)$.

First, suppose there exists a blue edge $vy \in E_H(\{v\}, A)$. Then $y \neq x$ (by assumption) and $y \neq x_2$ and $yx \notin E(G)$ (for otherwise $uvyx$ is a $C_4$). Since $vy$ must be within distance 2 of the (blue) edges in $E_H(\{x\}, B)$, it follows that $y$ must be adjacent to both blue neighbours $x_1^*, x_2^*$ of $x$ in $B$. But then $x x_1^* x_2^* y$ forms a $C_4$. Contradiction. So we conclude that $E_H(\{v\}, A) = \emptyset$. Second, suppose there is an edge $yy^* \in E_H(A_v, B)$, with $y \in A_v$ and $y^* \in B$. Let $z_1^*, z_2^*$ be two blue neighbours of $x$ in $B$ and let $z_3^*$ be a blue neighbour of $x_2$ in $B$. Recall that $x x_2 \in E(G)$ and, as before, $y \notin \{x, x_2\}$ and $yx, yx_2 \notin E(G)$. So in order to have $yy^*$ within distance 2 of $xz_1^*, xz_2^*$ and $x_2 z_3^*$, we must have for all $i \in \{1, 2, 3\}$ that either $y^* z_i^* \in E(G)$ or $y^* = z_i^*$, and $y^*$ can be equal to only one of the $z_i^*$. If $y^* = z_3^*$ then $xz_1^* z_2^* y^*$ will form a $C_4$. On the other hand, if (without loss of generality) $y^* = z_1^*$, then $xy^* z_3^* x_2$ forms a $C_4$. Contradiction. We conclude that $E_H(A_v, B)$ must be empty too. It follows that all edges of $H$ are incident to the triangle $uxx_2$, so $e(H) \le 3(\Delta - 1)$.

**Subsubcase 2.2.2.** $vx \in E(G)$.

By the argument of Subsubcase 2.1.2, $E_H(A_v, B) = \emptyset$.

**Subsubsubcase 2.2.2.1.** $E_H(\{v\}, A_v) \neq \emptyset$.

Let $vy \in E_H(\{v\}, A_v)$ and $x_2 x_2^* \in E_H(A_u, B)$. Since $x_2 y, vx_2 \notin E(G)$ (otherwise $uvyx_2$ or $uvx_2 x$ is a $C_4$), we must have $yx_2^* \in E(G)$. This holds for all such pairs, so in order to prevent a $C_4$, we must have $e_H(\{v\}, A_v) + e_H(\{x_2\}, B) \le 2$. So $e(H) \le e_H(\{v\}, A_v) + e_H(\{x_2\}, B) + |N_H(x) \cup N_H(u)| + e_H(A_v, B) \le 2 + (2\Delta - 1) + 0 = 2\Delta + 1$. This is bounded from above by $3(\Delta - 1)$ if $\Delta \ge 4$, which holds in this subcase because $x$ is adjacent to $u, v, x_2$ and its two or more neighbours in $B$.

**Subsubsubcase 2.2.2.2.** $E_H(\{v\}, A_v) = \emptyset$.

In this case all edges of $H$ are incident to the triangle $uxx_2$, so $e(H) \le 3(\Delta - 1)$. $\square$
# 6 Bipartite and two forbidden cycle lengths

In this section, we prove Theorem 10. Let us begin with the basic reduction from the {$C_3, C_5$}-free to the bipartite setting.

**Lemma 22.** Let $\mathcal{G}$ be a class of {$C_3, C_5$}-free graphs that is invariant under vertex-deletion. Let $\mathcal{G}_{\text{bip}}$ be the class of graphs in $\mathcal{G}$ that are bipartite. Then, provided both are well-defined, $\max_{G \in \mathcal{G}} \omega'_2(G) = \max_{G \in \mathcal{G}_{\text{bip}}} \omega'_2(G)$.

*Proof.* Clearly, $\max_{G \in \mathcal{G}_{\text{bip}}} \omega'_2(G) \le \max_{G \in \mathcal{G}} \omega'_2(G)$, so it remains to prove the converse. Given a graph $G$ in $\mathcal{G}$ we choose a subgraph $H$ of $G$ whose edges form a maximum clique in $L(G)^2$ and we choose an edge $uv \in E(H)$. Consider the induced subgraph $G^* := G[N(u) \cup N(v) \cup N(N[u]) \cup N(N[v])]$. The fact that $G$ is {$C_3, C_5$}-free implies that $G^* \in \mathcal{G}_{\text{bip}}$. Since $H$ is a subgraph of $G^*$ and moreover all possible edges (in $G$) between edges of $H$ are contained in $G^*$, it follows that $\omega(L(G^*)^2) = e(H) = \omega(L(G)^2)$. We conclude that $\max_{G \in \mathcal{G}} \omega'_2(G) = \max_{G \in \mathcal{G}} \omega'_2(G^*) \le \max_{G \in \mathcal{G}_{\text{bip}}} \omega'_2(G). \square$

Thus for Theorem 10 it suffices to prove the following result.

**Theorem 23.** For a {$C_{2k}, C_{2k+2}$}-free bipartite graph $G$ with $\Delta_G = \Delta$, $\omega'_2(G) \le \max\{k\Delta, 2k(k-1)\}$.

*Proof.* Let $G = G[X \times Y]$ be bipartite and {$C_{2k}, C_{2k+2}$}-free with $\Delta_G = \Delta$. By Theorem 5, we may assume throughout that $k \le \Delta$. Let $H$ be a subgraph of $G$ whose edges form a maximum clique in $L(G)^2$, so that $e(H) = \omega(L(G)^2)$. A path in $G$ will be called $H$-sided if it starts and ends on edges of $H$. Given a vertex $v \in V(G)$, an $H$-neighbour of $v$ is a vertex $w \in N_H(v)$.

Assume that $\omega(L(G)^2) > \max\{k\Delta, 2k(k-1)\}$. Under this assumption, we want to derive that for any $H$-sided path $P$ of order smaller than $2k+1$, we can find another $H$-sided path that has order $|P|+1$ or $|P|+2$, which is sufficient by the following claim.

**Claim 24.** Suppose that for each $H$-sided path $P$ in $G$ of order $|P| < 2k+1$, we can find another $H$-sided path of order $|P|+1$ or $|P|+2$. Then $G$ contains $P_{2k+1}$ as a subgraph, and also contains a copy of $C_{2k+2}$ or $C_{2k}$.

*Proof.* Because $e(H) \ge 1$, there exists an $H$-sided path of order 2. We can iteratively extend the length of this path by 1 or 2, ultimately yielding an $H$-sided path $P$ of order in {$2k+1, 2k+2$}. In particular, $G$ contains a path of order $2k+1$, as desired. The first and final edge of $P$ are in $H$ and therefore (also using that $|P| \ge 2k+1 \ge 5$) they must be at distance exactly 2. Since $G$ is bipartite, this implies the existence of a cycle of order in {$|P|, |P|-2$} if $|P|$ is even, and a cycle of order $|P|-1$ if $|P|$ is odd. So $G$ has a cycle of order in {$2k, 2k+2$}. $\diamond$
Let $P$ be an $H$-sided path. For clarity of notation we assume from now on that $P$ has even order $2\ell$, for some $\ell \le k$. For paths of odd order $< 2k+1$ the arguments are similar and in fact slightly easier, because the bounds we need are slightly more forgiving in that case. Write $P = p_1p_2 \dots p_{2\ell}$.

First, we need to introduce some definitions. Let $X_P = X \cap V(P) = p_1p_3 \dots p_{2\ell-1}$ and $Y_P = Y \cap V(P) = p_2p_4 \dots p_{2\ell}$ be the two parts of the bipartite graph induced by $P$. A vertex of $P$ will be called $r$-extravert if its number of $H$-neighbours outside $P$ is at least $r$. For short, we call the vertex *extravert* if it is 1-extravert. Conversely, a vertex of $P$ is *introvert* if all of its $H$-neighbours are in $P$. By $P_{\text{ex}}^{(r)}$ and $P_{\text{ex}}$ we denote the set of $r$-extravert vertices and extravert vertices respectively, and $P_{\text{in}}$ denotes the set of introvert vertices. Finally, by $\text{Obs}(P)$ we will denote the set of obsolete edges, which by definition are those edges of $H$ that are incident to some vertex of $P \setminus \{p_1, p_{2\ell}\}$. We call them obsolete because they cannot be 'greedily' used to extend the order of $P$.

From now on, suppose for a contradiction that it is not possible to find an $H$-sided path of order $|P|+1$ or $|P|+2$. Then the following claims hold.

**Claim 25.** The first and final vertex of $P$ are introvert.

*Proof.* Suppose by symmetry that the first vertex $p_1$ is extravert. Then it has an $H$-neighbour $p_0$ outside $P$, so $p_0P$ is an $H$-sided path of order $|P|+1$. Contradiction.
$\diamond$

**Claim 26.** $|\text{Obs}(P)| > \max\{k\Delta, 2k(k-1)\}$.

*Proof.* Suppose not. Then $|\text{Obs}(P)| \le \max\{k\Delta, 2k(k-1)\} < e(H)$. Therefore there exists an edge $e^*$ in $H$ that is not incident to any vertex of $P$. The final edge $e$ of $P$ is in $H$, so $e^*$ and $e$ must be at distance *exactly* 2. This implies that we can extend $P$ to an $H$-sided path (ending on $e^*$ rather than $e$) that is of order $|P|+1$ or $|P|+2$. Contradiction.
$\diamond$

So in order to arrive at a contradiction, it suffices to show that either $|\text{Obs}(P)| \le k\Delta$ or $|\text{Obs}(P)| \le 2k(k-1)$. We will now derive some structural properties of our counterexample.

**Claim 27.** Any two extravert vertices in the same part (both in $X_P$ or both in $Y_P$) have a common neighbour outside $P$.

*Proof.* Indeed, suppose without loss of generality that $p_i, p_j$ are two extravert vertices in $X_P$, with $H$-neighbours $q_i$ respectively $q_j$ outside $P$. If $q_i = q_j$ we are done, so suppose $q_i \ne q_j$. The edges $p_iq_i$ and $p_jq_j$ need to be within distance 2. Since odd cycles are not allowed in $G$, it follows that $p_i p_j, q_i q_j \notin E(G)$, so $q_i$ or $q_j$ must be a common neighbour of $p_i$ and $p_j$. $\diamond$
<figure><img src="image_4.png" /><figcaption>Figure 2: A depiction of the contradictory path-extensions described by Claim 28 (left) and Claim 32 (right). On the right, $a$ and $b$ are non-adjacent 3-extravert vertices and the subpath of $P$ between $a$ and $b$ has order 6. This means that $a$ and $b$ are too close to each other, with respect to $P$. Indeed, by following the green edges (and two blue edges) rather than the red edges, we obtain an $H$-sided path of order $|P| + 2$.</figcaption></figure>

**Claim 28.** *P* contains at most two pairs of consecutive extravert vertices, and if there are two such pairs $p_i p_{i+1}$ and $p_j p_{j+1}$, then they must have different parity, in the sense that $i = j + 1 \pmod 2$.

*Proof.* Suppose there are two extravert pairs $p_i p_{i+1}$, $p_j p_{j+1}$ of the same parity. Then without loss of generality $i + 1 < j$ and $p_i, p_j \in X_P$ and $p_{i+1}, p_{j+1} \in Y_P$. See Figure 2. By Claim 27, $p_i$ and $p_j$ have a common neighbour $u \in Y \setminus Y_P$, and $p_{i+1}$ and $p_{j+1}$ have a common neighbour $v \in X \setminus X_P$. Therefore we can replace the subpath $P^* = p_i p_{i+1} \dots p_j p_{j+1}$ of $P$ by $p_i u p_j p_{j-1} \dots p_{i+2} p_{i+1} v p_{j+1}$, which uses the same vertices as $P^*$ and two extra vertices $u, v$ outside of $P$. Thus, we have constructed an $H$-sided path of order $|P| + 2$. Contradiction. $\diamond$

The next claim is arguably the heart of the argument.

**Claim 29.** *There are at most $\ell$ extravert vertices.*

*Proof.* Consider the vertex pairs $(p_2, p_3)$, $(p_4, p_5)$, \dots, $(p_{2\ell-2}, p_{2\ell-1})$. By Claim 25, all extravert vertices are contained in the union of these $\ell - 1$ pairs. So if there are more than $\ell$ extravert vertices, then by the pigeonhole
principle at least two pairs entirely consist of extravert vertices. We have obtained two same-parity pairs of consecutive extravert vertices, contradicting Claim 28.

◇

From now on, let $r \ge 0$ be the maximal integer (if it exists) such that there are nonadjacent $r$-extravert vertices $s, t$ with $s \in X_P$ and $t \in Y_P$.

**Claim 30.** *The integer r is well-defined.*

*Proof.* Suppose $r$ does not exist. Then the vertices of $P$ induce a complete bipartite graph, with parts $X_P$ and $Y_P$. By Claim 29 we have $|P_{ex}| \le l$, and therefore $|\text{Obs}(P)| \le |X_P||Y_P| + |P_{ex}|(\Delta - \min\{|X_P|, |Y_P|\}) = l^2 + l(\Delta - l) \le k\Delta$, contradicting Claim 26.

◇

The next claim follows directly from the definition of $r$.

**Claim 31.** *The graph induced by $P_{ex}^{(r+1)}$ is complete bipartite.*

Next, we show that highly extravert vertices of different parity cannot be too close to eachother with respect to $P$.

**Claim 32.** *Let $q$ be a positive integer. Let $a \in X_P, b \in Y_P$ be two non-adjacent $q$-extravert vertices. Then the subpath of $P$ having endpoints $a$ and $b$ has at least $2q + 2$ vertices.*

*Proof.* Suppose for a contradiction that the subpath of $P$ with endpoints $a$ and $b$ has (even) order $d \le 2q$. Let $A = \{a_1, \dots, a_q\}$ denote a subset of the $H$-neighbours of $a$ in $Y \setminus Y_P$. Similarly, let $B = \{b_1, \dots, b_q\}$ denote a subset of the $H$-neighbours of $b$ in $X \setminus X_P$. See Figure 2. Because $ab \notin E(G)$ and the $H$-edges $a_ia, b_jb$ should be within distance 2 for all $i, j$, it follows that $A$ is complete to $B$. Therefore there exists a path $P^* = aa_1b_1a_2b_2 \dots a_qb_qb$ of order $d+2$ that only intersects $P$ in $a$ and $b$. This leads to a contradiction, because it implies that we can construct an $H$-sided path of order $|P| + 2$, by replacing the order $d$ subpath of $P$ between $a$ and $b$ with the order $d+2$ path $P^*$.

◇

With the above claims, we now complete the proof of Theorem 23 by deriving a contradiction to Claim 26.

We partition the vertices of $P$ and estimate the $H$-edges incident to them separately. First we need some definitions. Let $i_x = |P_{ex}^{(r+1)} \cap X_P|$ and $i_y = |P_{ex}^{(r+1)} \cap Y_P|$ be the numbers of $(r+1)$-extravert vertices in the parts $X_P, Y_P$ of the bipartite graph induced by $P$. Similarly, let $j_x = |P_{ex} \setminus P_{ex}^{(r+1)} \cap X_P|$ and $j_y = |P_{ex} \setminus P_{ex}^{(r+1)} \cap Y_P|$ be the number of vertices that are extravert but not $(r+1)$-extravert, in part $X_P$ respectively $Y_P$. Note that the remaining $|X_P| - i_x - j_x$ (resp. $|Y_P| - i_y - j_y$) vertices in $X_P$ (resp. $Y_P$) are introvert.
An important observation is that we can write $\text{Obs}(P)$ as a disjoint union $E_1 \cup E_2 \cup E_3$, where

$$E_1 = I_H(P_{\text{ex}}^{(r+1)}), \quad E_2 = I_H(P_{\text{ex}}) \setminus I_H(P_{\text{ex}}^{(r+1)}), \quad \text{and} \quad E_3 = E(H[P_{\text{in}}]).$$

Recall from Claim 31 that $G[P_{\text{ex}}^{(r+1)}]$ is complete bipartite, so it is efficient to estimate $|E_1|$ by summing the degrees (with respect to $G$) of $P_{\text{ex}}^{(r+1)}$ and subtracting the double-counted edges of $G[P_{\text{ex}}^{(r+1)}]$. This yields

$$|E_1| \le -e(G[P_{\text{ex}}^{(r+1)}]) + \sum_{v \in P_{\text{ex}}^{(r+1)}} |N_G(v)| \le -i_x i_y + (i_x + i_y)\Delta. \quad (4)$$

To estimate $|E_2|$, note that it is maximised if each vertex $v \in P_{\text{ex}} \setminus P_{\text{ex}}^{(r+1)}$ has exactly $r$ H-neighbours outside $G[P]$ and is incident to all vertices of the opposite part that are not in $P_{\text{ex}}^{(r+1)}$ (and leaving out one single edge from this graph, to comply with the non-edge that defines $r$). In this case

$$\begin{aligned} |E_2| &\le -e(H[P_{\text{ex}} \setminus P_{\text{ex}}^{(r+1)})] + \sum_{v \in P_{\text{ex}} \setminus P_{\text{ex}}^{(r+1)}} |N_H(v) \setminus P_{\text{ex}}^{(r+1)}| \quad (5) \\ &\le -j_x j_y + j_x(r + |Y_P| - i_y) + j_y(r + |X_P| - i_x). \end{aligned}$$

The quantity $|E_3|$ is maximised if $P_{\text{in}}$ induces a complete bipartite graph, so

$$|E_3| \le (|X_P| - i_x - j_x)(|Y_P| - i_y - j_y). \quad (6)$$

Summing estimates (4), (5) and (6), we conclude that

$$\begin{aligned} |\text{Obs}(P)| &\le (i_x + i_y)\Delta + (j_x + j_y)r + |X_P||Y_P| - i_x|Y_P| - i_y|X_P| \\ &= (i_x + i_y)(\Delta - \ell) + (j_x + j_y)r + \ell^2. \end{aligned} \quad (7)$$

If $\Delta - \ell \ge r$ then (7) is maximised for $j_x + j_y = 0$, so that $i_x + i_y = |P_{\text{ex}}|$. This means that all extravert vertices are in fact $(r+1)$-extravert. By Claim 29,

$$|\text{Obs}(P)| \le |P_{\text{ex}}|(\Delta - \ell) + \ell^2 \le \ell(\Delta - \ell) + \ell^2 \le k\Delta,$$

a contradiction to Claim 26. Conversely, if $\Delta - \ell < r$ then the upper bound on $|\text{Obs}(P)|$ is maximised for $i_x + i_y = 0$, so that $j_x + j_y = |P_{\text{ex}}|$. This means that none of the extravert vertices is $(r+1)$-extravert. By Claim 29, we again obtain a contradiction to Claim 26:

$$|\text{Obs}(P)| \le |P_{\text{ex}}|r + \ell^2 \le \ell(\ell - 2) + \ell^2 \le 2k(k - 1).$$

In the last line, we used that $r \le \ell - 2$, which follows from Claim 32 and the fact that the first and final vertex of $P$ are introvert. $\square$
References

[1] H. Bruhn and F. Joos. A stronger bound for the strong chromatic index. *Combin. Probab. Comput.*, 27(1):21–43, 2018.

[2] P. Erdős. Problems and results in combinatorial analysis and graph theory. In *Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986)*, volume 72, pages 81–92, 1988.

[3] P. Erdős and T. Gallai. On maximal paths and circuits of graphs. *Acta Math. Acad. Sci. Hungar*, 10:337–356 (unbound insert), 1959.

[4] 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. To appear in *Journal of Graph Theory*, 2019.

[5] R. J. Faudree, A. Gyárfás, R. H. Schelp, and Z. Tuza. Induced matchings in bipartite graphs. *Discrete Math.*, 78(1-2):83–87, 1989.

[6] R. J. Faudree, R. H. Schelp, A. Gyárfás, and Z. Tuza. The strong chromatic index of graphs. *Ars Combin.*, 29(B):205–211, 1990. Twelfth British Combinatorial Conference (Norwich, 1989).

[7] R. J. Kang and F. Pirot. Distance colouring without one cycle length. *Combin. Probab. Comput.*, 27(5):794–807, 2018.

[8] M. Mahdian. The strong chromatic index of $C_4$-free graphs. *Random Structures Algorithms*, 17(3-4):357–375, 2000.

[9] M. Molloy and B. Reed. A bound on the strong chromatic index of a graph. *J. Combin. Theory Ser. B*, 69(2):103–109, 1997.

[10] M. Śleszyńska-Nowak. Clique number of the square of a line graph. *Discrete Math.*, 339(5):1551–1556, 2016.

[11] V. H. Vu. A general upper bound on the list chromatic number of locally sparse graphs. *Combin. Probab. Comput.*, 11(1):103–111, 2002.