In this paper, we prove that if a graph does not contain any cycle of length greater than \(4\), then the square of its line graph is perfect. As an application, we give a concise proof of a known result: the strong chromatic index of a bipartite graph that does not contain any cycle of length greater than \(4\) is at most \(\Delta^2\), where \(\Delta\) represents the maximum degree of the graph. This latter result provides a partial affirmative answer to some known conjectures on upper bounds for the strong chromatic index of graphs.
Throughout this paper, by a graph we mean a finite undirected graph that has no loops or multiple edges. Given the graph \(G\), we denote the set of vertices and the set of edges of \(G\) by \(V(G)\) and \(E(G)\), respectively. For terminology and concepts not given here, the reader may refer to [11] and [21].
We begin the paper by introducing the notion of an induced subgraph, which plays a central role in our discussion. An induced subgraph of a graph \(G\) is a graph \(H\) formed by taking \(V(H)\) as a nonempty subset of \(V(G)\) and \(E(H)\) as all of the edges in \(G\) connecting pairs of vertices in \(V(H)\). In particular, an induced cycle in \(G\) is a cycle of \(G\) that is an induced subgraph of \(G\).
A proper vertex-coloring of a graph \(G\) is an assignment of colors to the vertices of \(G\) in such a way that no two adjacent vertices share a common color. The minimum number of colors that allow a proper vertex-coloring of \(G\) is called the chromatic number of \(G\) and is denoted by \(\chi(G)\). A list of well-studied coloring parameters of graphs can be found in [13].
A clique in the graph \(G\) is a subset of vertices in \(G\) such that every two distinct vertices in the clique are adjacent. A maximum clique is a clique that has the largest possible number of vertices. The clique number of \(G\) is the number of vertices in a maximum clique of \(G\) and is denoted by \(\omega (G)\).
It is known that the problem of finding the parameters \(\chi(G)\) and \(\omega(G)\) is NP-hard (see [10]). As every vertex of a clique should get a different color, it is obvious that \(\chi(G) \ge \omega(G)\). It is also easy to see that \(\chi(G)\) may be greater than \(\omega(G)\). For example, \(\chi (C_5) = 3 > 2 = \omega (C_5)\), where \(C_5\) is the cycle of length \(5\). Based on the above notions and observations, it seems natural to ask when does the equality \(\chi(G) = \omega (G)\) hold. For a graph \(G\), it is known that determining whether the equality \(\chi(G) = \omega(G)\) holds is an NP-complete problem (see [15]). A graph \(G\) is called perfect provided \(\chi(H) = \omega (H)\) holds true for every induced subgraph \(H\) of \(G\). The strong perfect graph theorem, one of the foundational results in graph theory, says that a graph is perfect if and only if neither the graph nor its complement contains an induced odd cycle of length at least \(5\) (see [5]).
A graph is said to be \(4\)-chordal if it does not contain induced cycles of length greater than \(4\). It is worthwhile to note that \(4\)-chordal graphs are also called long-hole-free graphs (see, for example, [4]). A graph is said to be chordal if every cycle of length \(4\) or more has a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.
The line graph \(L(G)\) of the graph \(G\) is the graph with vertex set \(E(G)\) such that two vertices are adjacent in \(L(G)\) if and only if the corresponding edges of \(G\) have a common vertex. A graph \(G\) is a line graph if it is isomorphic to the line graph \(L(H)\) of some graph \(H\).
For a graph \(G\), its square, denoted by \(G^2\), has vertex set \(V(G)\) and two vertices are adjacent in \(G^2\) exactly when they are joined by an edge or a path of two edges in \(G\). The graph \(L(G)^2\) is the square of the line graph of \(G\), that is, the vertex set of \(L(G)^2\) is \(E(G)\) and two vertices are adjacent in \(L(G)^2\) if and only if the corresponding edges of \(G\) share a vertex or are connected by an edge in \(G\).
We are now in the position to present the main result of this paper.
Theorem 1.1 (Theorem A). Let \(G\) be a graph that does not contain any cycle of length greater than \(4\). Then \(L(G)^2\) is perfect.
While chordal graphs are perfect by a theorem of Dirac [6], Theorem 1.1 (Theorem A) is not an immediate consequence: indeed \(L(G)^2\) need not be chordal even when \(G\) does not contain any cycle of length greater than \(4\). The graph presented in Figure 1 provides a counterexample (see [19, Theorem 4.1]).
It is worthwhile to note that previous work by Hatzel and Wiederrecht [12, Theorem 24] provided necessary and sufficient conditions for \(L(G)^2\) to be perfect, including a necessary condition requiring the graph \(G\) to have no induced cycle of length at least \(7\). The absence of such long induced cycles is not sufficient by itself; additional forbidden configurations are required (see [12]). Theorem 1.1 (Theorem A), by contrast, shows that the stronger assumption that \(G\) contains no cycle of length greater than \(4\) is sufficient for \(L(G)^2\) to be perfect.
The rest of the paper is organized as follows. In Section 2, we provide a proof of Theorem 1.1 (Theorem A). In Section 3, we apply Theorem 1.1 (Theorem A) to give a concise proof of a known upper bound for the strong chromatic index of bipartite graphs without cycles longer than \(4\).
In a paper published in 1970, Beineke [1] obtained a characterization of line graphs in terms of nine forbidden induced subgraphs. Since the complete bipartite graph \(K_{1,3}\) is one of those forbidden subgraphs, line graphs cannot contain it as an induced subgraph. Let us now formally state this result for future reference.
Lemma 2.1. Let \(G\) be a graph. Then the line graph \(L(G)\) cannot contain a \(K_{1,3}\) as an induced subgraph.
In what follows, when we deal with cycles of length \(n\), we always take the indices modulo \(n\). By this convention, we may give the following definition.
Definition 2.2. Let \(G\) be a graph with edges \(e_1, \ldots, e_n\) such that \(C = e_1 e_2 \ldots e_n e_1\) is an induced cycle of length \(n \ge 4\) in \(L(G)^2\). Then, obviously, \(e_1, \ldots, e_n\) are all vertices of \(L(G)\) and we may define the set \(\mathfrak{A} (C)\) as follows: \[\mathfrak{A} (C) = \big \{1 \le i \le n \mid e_i \text{ is not adjacent to } e_{i+1} \text{ in } L(G) \big\}.\]
We will need the following lemma to avoid repetition in the proofs later on.
Lemma 2.3. Let \(G\) be a graph and \(C = e_1 e_2 \ldots e_n e_1\) be an induced cycle of length \(n \ge 4\) in \(L(G) ^2\). Then the following statements hold:
(a) For every \(1 \le i \le n\), \(e_i\) is not adjacent to \(e_j\) in \(L(G)\) for \(j \ne i \pm 1\).
(b) The set \(\{1, \ldots, n\} \setminus \mathfrak{A} (C)\) does not contain consecutive numbers and \(\lceil \frac{n}{2} \rceil \le |\mathfrak{A} (C)| \le n\).
(c) For every \(i \in \mathfrak{A} (C)\), there exists a vertex \(x_i\) of \(L(G)\) which is adjacent to both \(e_i\) and \(e_{i+1}\) in \(L(G)\). Moreover,
(i) the vertex \(x_i\) is not adjacent to \(e_j\) in \(L(G)\) for \(j \ne i, i+1\), and
(ii) if, for \(j \in \mathfrak{A} (C)\), \(x_i\) is adjacent to \(x_j\) in \(L(G)\), then \(j = i \pm 1\).
Proof. (a) Suppose that \(e_i\) and \(e_j\) are adjacent in \(L(G)\) for \(j \ne i \pm 1\). Then \(e_i\) and \(e_j\) are adjacent in \(L(G)^2\) and \(e_ie_j\) is a chord of \(C\), which is a contradiction.
(b) Let \(1 \le i \le n\) be given. Note that \(e_i\) may or may not be adjacent to \(e_{i+1}\) in \(L(G)\). If \(e_i\) is adjacent to \(e_{i+1}\), then \(e_{i+1}\) cannot be adjacent to \(e_{i+2}\); otherwise, \(e_i\) would be adjacent to \(e_{i+2}\) in \(L(G) ^2\), which is a contradiction. Therefore, the set \(\{1, \ldots, n\} \setminus \mathfrak{A} (C)\) does not contain consecutive integers and \(\lceil \frac{n}{2} \rceil \le| \mathfrak{A} (C)| \le n\).
(c) For every \(i \in \mathfrak{A} (C)\), since \(e_i\) is not adjacent to \(e_{i+1}\) in \(L(G)\) but is adjacent to \(e_{i+1}\) in \(L(G)^2\), there exists a vertex \(x_i\) of \(L(G)\) such that \(x_i\) is adjacent to both \(e_i\) and \(e_{i+1}\) in \(L(G)\). Moreover, we have the following:
(i) The vertices \(x_i\) and \(e_j\) are not adjacent in \(L(G)\) for \(j \ne i, i+1\); otherwise, either \(e_i\) is adjacent to \(e_j\) in \(L(G)^2\) for \(j\ne i, i\pm 1\), or \(e_{i+1}\) is adjacent to \(e_{i-1}\) in \(L(G)^2\), both of which are contradictions.
(ii) Since adjacency in \(L(G)\) means that the corresponding edges of \(G\) share a common vertex, the adjacency of \(x_i\) and \(x_j\) in \(L(G)\) implies that the edges of \(G\) corresponding to \(x_i\) and \(x_j\) are incident to a common vertex.
Now \(x_i\) is adjacent in \(L(G)\) to \(e_i\) and \(e_{i+1}\), while \(x_j\) is adjacent in \(L(G)\) to \(e_j\) and \(e_{j+1}\). Moreover, since \(i,j\in \mathfrak {A}(C)\), the pairs \(e_i, e_{i+1}\) and \(e_j, e_{j+1}\) are not adjacent in \(L(G)\); hence, each pair consists of two edges of \(G\) with distinct endpoints. Therefore, if the edges corresponding to \(x_i\) and \(x_j\) share a vertex in \(G\), that vertex must also be an endpoint of one of \(e_j\) or \(e_{j+1}\). In other words, \(x_i\) must be adjacent in \(L(G)\) to \(e_j\) or \(e_{j+1}\). By part (i), \(x_i\) is adjacent only to \(e_i\) and \(e_{i+1}\) in \(L(G)\). Hence, \(j \in \{i,i+1\}\) or \(j+1 \in \{i,i+1\}\). Since \(i \ne j\), it follows that \(j = i \pm 1\). \(\square\)
Definition 2.4. With the set-up of Definition 2.2, for each \(i \in \mathfrak {A}(C)\), we call the vertex \(x_i\) given by Lemma 2.3(c) a bridging vertex.
In order to prove Theorem 1.1 (Theorem A), we will also need the following lemma which enables us to construct induced cycles in line graphs.
Lemma 2.5. Let \(G\) be a graph. If \(C = e_1 e_2 \ldots e_n e_1\) is an induced cycle of length \(n \ge 4\) in \(L(G) ^2\), then \(L(G)\) contains an induced cycle of length \(\ge n\).
Proof. For each \(i \in \mathfrak{A}(C)\), let \(x_i\) be the bridging vertex of \(L(G)\) given by Lemma 2.3(c) (see Definition 2.4). By part (ii) of Lemma 2.3(c), adjacency among the vertices \(\{x_i \mid i \in \mathfrak{A} (C)\}\) can occur only between consecutive indices, that is, if \(x_i x_j\) are adjacent in \(L(G)\), then \(j = i \pm 1\). We will construct an induced cycle \(C'\) in \(L(G)\) with length \(\ge n\). In order to do this, consider \[W = \{e_{i+1} \mid i, i+1 \in \mathfrak{A} (C) \text{ and } x_i \text{ is adjacent to } x_{i+1} \text{ in } L(G) \},\] and define the set of vertices of \(C'\) by \[V = \big( \{e_i \mid 1 \le i \le n\} \setminus W \big) \cup \{x_i \mid i \in \mathfrak {A} (C)\}.\] We now define a cyclic ordering of \(V\) in \(L(G)\). Note that in each case, any vertex belonging to \(W\) is omitted.
\(\circ\) If \(i\notin \mathfrak{A}(C)\), retain the edge \(e_i e_{i+1}\).
\(\circ\) If \(i\in\mathfrak{A}(C)\) and \(i+1\notin \mathfrak{A}(C)\), replace \(e_i e_{i+1}\) by \(e_ix_ie_{i+1}\).
\(\circ\) If \(i,i+1\in \mathfrak{A}(C)\), then replace the segment through \(e_{i+1}\) as follows:
if \(x_i\) is adjacent to \(x_{i+1}\) in \(L(G)\), use \(e_i x_i x_{i+1} e_{i+2}\);
otherwise, use \(e_i x_i e_{i+1} x_{i+1} e_{i+2}\).
By Lemma 2.3(a), the vertices \(e_1,\ldots,e_n\) are pairwise nonadjacent in \(L(G)\) except for consecutive indices. By Lemma 2.3(c), each bridging vertex \(x_i\) is adjacent precisely to \(e_i\) and \(e_{i+1}\), and possible adjacencies among bridging vertices occur only between consecutive indices. Therefore, no additional adjacencies occur among the vertices of \(C'\) beyond those explicitly listed, and each vertex in the induced subgraph has degree exactly \(2\). Hence, the resulting graph \(C'\) is an induced cycle in \(L(G)\).
Finally, consider the length of \(C'\). Observe that whenever a vertex \(e_{i+1}\) is omitted (that is, when \(e_{i+1} \in W\)), it is replaced by at least two vertices \(x_i\) and \(x_{i+1}\). In all other cases, either one vertex in inserted or the original adjacency is retained. Thus, every replacement described above either preserves the number of vertices in the segment or increases it. Hence, \(|V(C')|\ge n\). This completes the proof. \(\square\)
The following lemma will also be used repeatedly in the remainder of this paper.
Lemma 2.6 ([19], Lemma 3.1). Let \(G\) be a graph. Then \(G\) contains a cycle \(C\) of length at least \(4\) if and only if the line graph \(L(G)\) contains an induced cycle \(C_L\) of the same length.
It is worthwhile to note that the cycle \(C\) of \(G\) in Lemma 2.6 is not necessarily induced. Figure 2 presents such an example: here \(G\) is \(4\)-chordal, yet its line graph \(L(G)\) contains an induced cycle of length greater than \(4\).
Lemma 2.7. Let \(G\) be a graph that does not contain any cycle of length greater than \(4\). If \(C = e_1 e_2 e_3 e_4 e_1\) is an induced cycle in \(L(G)^2\), then \(|\mathfrak{A} (C)| = 4\).
Proof. By Lemma 2.3(b), the set \(\{1, 2, 3, 4\} \setminus \mathfrak{A} (C)\) does not contain consecutive integers and also \(|\mathfrak{A} (C)|\) is equal to 2, 3 or 4.
Case I. \(|\mathfrak{A} (C)| = 2\). In this case, by the above observation, without loss of generality, we may assume that \(\{1, 2, 3, 4\} \setminus \mathfrak{A} (C) = \{1, 3\}\), and so, \(\mathfrak{A} (C) = \{2, 4\}\). Therefore, by Lemma 2.3(c), there exist bridging vertices \(x_2\) and \(x_4\) of \(L(G)\). By part (ii) of Lemma 2.3(c), \(x_2\) is not adjacent to \(x_4\) in \(L(G)\), and so, by Definition 2.2 and parts (a) and (c) of Lemma 2.3, \(e_1 e_2 x_2 e_3 e_4 x_4 e_1\) is an induced cycle in \(L(G)\) with length \(6\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(6\), a contradiction.
Case II. \(|\mathfrak{A} (C)| = 3\). In this case, without loss of generality, we may assume that \(\mathfrak{A} (C) = \{2, 3, 4\}\). Therefore, by Lemma 2.3(c), there exist bridging vertices \(x_2\), \(x_3\) and \(x_4\) of \(L(G)\). If none of the \(x_i\)’s are adjacent in \(L(G)\), then by Definition 2.2 and parts (a) and (c) of Lemma 2.3, \(e_1 e_2 x_2 e_3 x_3 e_4 x_4 e_1\) is an induced cycle of length \(7\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(7\), a contradiction. Note that, by part (ii) of Lemma 2.3(c), \(x_2\) is not adjacent to \(x_4\) in \(L(G)\). If \(x_2\) is adjacent to \(x_3\) and \(x_3\) is not adjacent to \(x_4\) in \(L(G)\), then by Definition 2.2 and parts (a) and (c) of Lemma 2.3, \(e_1 e_2 x_2 x_3 e_4 x_4 e_1\) is an induced cycle of length \(6\) in \(L(G)\). Again, by Lemma 2.6, this implies that \(G\) has a cycle of length \(6\), a contradiction. If \(x_2\) is not adjacent to \(x_3\) but \(x_3\) is adjacent to \(x_4\) in \(L(G)\), then by the same argument as above we are led to a contradiction. Finally, if \(x_2\) is adjacent to \(x_3\) and \(x_3\) is adjacent to \(x_4\) in \(L(G)\), then by Lemma 2.3(c), \(e_1 e_2 x_2 x_3 x_4 e_1\) is an induced cycle of length \(5\) in \(L(G)\). By Lemma 2.6, this implies that \(G\) has a cycle of length \(5\), again a contradiction.
Since the above two cases lead to a contradiction, we conclude that \(|\mathfrak{A} (C)| = 4\). \(\square\)
Lemma 2.8. Let \(G\) be a graph that does not contain any cycle of length greater than \(4\), and let \(C = e_1 e_2 e_3 e_4 e_1\) be an induced cycle in \(L(G)^2\). Then the following statements hold:
(a) The edges \(e_1,e_2,e_3,e_4\) are pairwise nonadjacent in \(L(G)\).
(b) For each \(i \in \{1,2,3,4\}\), there exists a vertex \(x_i\) of \(L(G)\) such that
(i) \(x_i\) is adjacent to both \(e_i\) and \(e_{i+1}\) in \(L(G)\), and
(ii) \(x_i\) is adjacent to neither \(e_{i+2}\) nor \(e_{i+3}\) in \(L(G)\).
(c) Among the vertices \(x_1,x_2,x_3,x_4\), we have
(i) \(x_1\) is not adjacent to \(x_3\) in \(L(G)\),
(ii) \(x_2\) is not adjacent to \(x_4\) in \(L(G)\), and
(iii) for each \(i \in \{1,2,3,4\}\), the vertices \(x_i\) and \(x_{i+1}\) are adjacent in \(L(G)\).
Proof. First, note that, by Lemma 2.7, we have \(|\mathfrak A(C)|=4\), and hence, \(\mathfrak A(C) = \{1, 2, 3, 4\}\).
(a) By Definition 2.2 and Lemma 2.3(a), none of the \(e_i\)’s are adjacent to one another in \(L(G)\).
(b) By Lemma 2.3(c) and its first part, there exist bridging vertices \(x_1\), \(x_2\), \(x_3\) and \(x_4\) of \(L(G)\) such that for every \(i \in \{1, 2, 3, 4\}\), \(x_i\) is adjacent to both \(e_i\) and \(e_{i+1}\) in \(L(G)\) but is not adjacent to \(e_{i+2}\) or \(e_{i+3}\).
(c) By part (ii) of Lemma 2.3(c), \(x_1\) is not adjacent to \(x_3\) and \(x_2\) is not adjacent to \(x_4\) in \(L(G)\). What remains is to prove that for every \(i \in \{1, 2, 3, 4\}\), \(x_i\) and \(x_{i+1}\) are adjacent in \(L(G)\). We now distinguish four cases; in each case we shall obtain a contradiction.
Case I. The vertices \(x_i\) and \(x_{i+1}\) are not adjacent in \(L(G)\) for every \(i \in \{1, 2, 3, 4\}\). Then \(e_1 x_1 e_2 x_2 e_3 x_3 e_4 x_4 e_1\) is an induced cycle of length \(8\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(8\), a contradiction.
Case II. The vertices \(x_i\) and \(x_{i+1}\) are adjacent in \(L(G)\) for exactly one \(i \in \{1, 2, 3, 4\}\). Without loss of generality, we may assume that \(x_1\) and \(x_2\) are adjacent in \(L(G)\) and this is the only edge between the \(x_i\)’s. Then \(e_1 x_1 x_2 e_3 x_3 e_4 x_4 e_1\) is an induced cycle of length \(7\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(7\), a contradiction.
Case III. The vertices \(x_i\) and \(x_{i+1}\) are adjacent in \(L(G)\) for exactly two \(i \in \{1, 2, 3, 4\}\). Without loss of generality, we may assume that the two edges are either \(x_1 x_2\) and \(x_2 x_3\) or \(x_1 x_2\) and \(x_3 x_4\). If the former occurs, then \(e_1 x_1 x_2 x_3 e_4 x_4 e_1\) is an induced cycle of length \(6\) in \(L(G)\). On the other hand, if the two edges are \(x_1 x_2\) and \(x_3 x_4\), then \(e_1 x_1 x_2 e_3 x_3 x_4 e_1\) is an induced cycle of length \(6\) in \(L(G)\). In either of the two possibilities, we have by Lemma 2.6 that \(G\) has a cycle of length \(6\), a contradiction.
Case IV. The vertices \(x_i\) and \(x_{i+1}\) are adjacent in \(L(G)\) for exactly three \(i \in \{1, 2, 3, 4\}\). Without loss of generality, we may assume that \(x_1\) is adjacent to \(x_2\), \(x_2\) is adjacent to \(x_3\) and \(x_3\) is adjacent to \(x_4\) in \(L(G)\), and these three edges are the only edges between the \(x_i\)’s. Then \(e_1 x_1 x_2 x_3 x_4 e_1\) is an induced cycle of length \(5\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(5\), a contradiction.
From the above cases, we deduce that the only possibility is that \(x_i\) and \(x_ {i+1}\) are adjacent in \(L(G)\) for every \(i \in \{1, 2, 3, 4\}\). \(\square\)
We prove two more lemmas before giving the proof of Theorem 1.1 (Theorem A).
Lemma 2.9. Let \(G\) be a graph that does not contain any cycle of length greater than \(4\). Then \(L(G)^2\) cannot contain the graph \(H\), presented in Figure 3, as an induced subgraph.
Proof. Suppose that \(L(G)^2\) contains the graph \(H\) as an induced subgraph. Therefore, \(L(G)^2\) contains the induced cycle \(e_1 e_2 e_3 e_4 e_1\). Now, by Lemma 2.8, there exist the bridging vertices \(x_1\), \(x_2\), \(x_3\) and \(x_4\) of \(L(G)\) which satisfy the conditions of Lemma 2.8. Note that \(e\) is a vertex of \(L(G)\) and we claim the following:
Claim 1. The vertex \(e\) is not adjacent to \(x_i\) in \(L(G)\) for \(1 \le i \le 4\).
Proof of Claim 1. First, note that \(e\) is adjacent to none of \(x_2\), \(x_3\) and \(x_4\) in \(L(G)\); otherwise, since \(x_2\) and \(x_3\) are adjacent to \(e_3\) and \(x_4\) is adjacent to \(e_4\) in \(L(G)\), \(e\) is adjacent to either \(e_3\) or \(e_4\) in \(L(G)^2\), which is in contradiction to \(H\) being an induced subgraph.
We also note that \(e\) is not adjacent to \(x_1\) in \(L(G)\); otherwise, by the observation in the previous paragraph and Lemma 2.8(c), \(L(G)\) contains a \(K_{1,3}\) as an induced subgraph with \(\{x_1\}\) and \(\{e, x_2, x_4\}\) as parts of the bipartition, which is in contradiction to Lemma 2.1. \(\square\)
We now consider the three cases: (I) the vertex \(e\) is adjacent to both \(e_1\) and \(e_2\) in \(L(G)\); (II) the vertex \(e\) is adjacent to only one of \(e_1\) and \(e_2\) in \(L(G)\); (III) the vertex \(e\) is adjacent to neither \(e_1\) nor \(e_2\) in \(L(G)\). We show below that each of these cases gives rise to a contradiction.
Case I. The vertex \(e\) is adjacent to both \(e_1\) and \(e_2\) in \(L(G)\). In this case, by Claim 1 and parts (a), (b) and (c) of Lemma 2.8, \(e_1 e e_2 x_2 x_3 x_4 e_1\) is an induced cycle of length \(6\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(6\), a contradiction.
Case II. The vertex \(e\) is adjacent to only one of \(e_1\) and \(e_2\) in \(L(G )\). In this case, we may suppose without loss of generality that \(e\) is not adjacent to \(e_1\) in \(L(G)\) but is adjacent to \(e_2\) in \(L(G)\). Since \(e\) is adjacent to \(e_1\) in \(L(G)^2\), there exists a vertex \(y_1\) of \(L(G)\) such that \(y_1\) is adjacent to both \(e_1\) and \(e\) in \(L(G)\). The next two claims will be useful in concluding that Case II is not possible.
Claim 2. The vertex \(y_1\) is adjacent to neither \(x_2\) nor \(x_3\) in \(L(G)\).
Proof of Claim 2. Suppose that \(y_1\) is adjacent to \(x_i\) in \(L(G)\) (\(i = 2\) or \(3\)). Then by Claim 1 and Lemma 2.8(b), \(L(G)\) contains a \(K_{1,3}\) as an induced subgraph with \(\{y_1\}\) and \(\{x_i, e_1, e\}\) as parts of the bipartition, which is in contradiction to Lemma 2.1. \(\square\)
Claim 3. The vertex \(y_1\) is not adjacent to \(e_2\) in \(L(G)\).
Proof of Claim 3. Suppose that \(y_1\) is adjacent to \(e_2\) in \(L(G)\). There are two possibilities: either \(y_1\) and \(x_4\) are adjacent in \(L(G)\) or they are not.
First, suppose that \(y_1\) and \(x_4\) are adjacent in \(L(G)\). Then by Claim 2 as well as parts (b) and (c) of Lemma 2.8, \(y_1 e_2 x_2 x_3 x_4 y_1\) is an induced cycle of length \(5\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(5\), a contradiction.
Now, suppose that \(y_1\) and \(x_4\) are not adjacent in \(L(G)\). Then again by Claim 2 as well as parts (a), (b) and (c) of Lemma 2.8, \(y_1 e_2 x_2 x_3 x_4 e_1 y_1\) is an induced cycle of length \(6\) in \(L(G)\). By Lemma 2.6, this implies that \(G\) has a cycle of length \(6\), again a contradiction.
Since both cases give us a contradiction, Claim 3 holds true. \(\square\)
Now, there are two possibilities: either \(y_1\) and \(x_4\) are adjacent in \(L(G)\) or they are not. If \(y_1\) and \(x_4\) are adjacent in \(L(G)\), then it follows by Claims 1, 2 and 3 as well as parts (b) and (c) of Lemma 2.8 that \(y_1 e e_2 x_2 x_3 x_4 y_1\) is an induced cycle of length \(6\) in \(L(G)\). By Lemma 2.6, this gives us a contradiction as it implies that \(G\) has a cycle of length \(6\). On the other hand, if \(y_1\) is not adjacent to \(x_4\) in \(L(G)\), then again by Claims 1, 2 and 3 as well as parts (a), (b) and (c) of Lemma 2.8, we have that \(y_1 e e_2 x_2 x_3 x_4 e_1 y_1\) is an induced cycle of length \(7\) in \(L(G)\). Again, by Lemma 2.6, we have a contradiction as this implies that \(G\) has a cycle of length \(7\).
These contradictions tell us that Case II does not occur. This leaves us with one remaining case to consider.
Case III. The vertex \(e\) is adjacent to neither \(e_1\) nor \(e_2\) in \(L(G)\). Since \(e\) is adjacent to both \(e_1\) and \(e_2\) in \(L(G)^2\), in this case, there exist vertices \(y_1\) and \(y_2\) of \(L(G)\) such that \(y_1\) is adjacent to both \(e_1\) and \(e\) whereas \(y_2\) is adjacent to both \(e_2\) and \(e\) in \(L(G)\). The following claims will enable us to conclude that Case III is not possible.
Claim 4. The vertex \(y_1\) is adjacent to none of \(e_2\), \(x_2\) and \(x_3\) in \(L(G)\).
Proof of Claim 4. Suppose to the contrary that \(y_1\) is adjacent to \(e_2\) in \(L(G)\). By Lemma 2.8(a), \(e_1\) and \(e_2\) are not adjacent in \(L(G)\). Therefore, \(L(G)\) contains a \(K_{1,3}\) as an induced subgraph with \(\{y_1\}\) and \(\{e_2, e_1, e\}\) as parts of the bipartition, which is in contradiction to Lemma 2.1.
Also, if \(y_1\) is adjacent to \(x_i\) in \(L(G)\) (\(i = 2\) or \(3\)), then by Claim 1 and Lemma 2.8(b), \(L(G)\) would contain a \(K_{1,3}\) as an induced subgraph with \(\{y_1\}\) and \(\{x_i, e_1, e\}\) as parts of the bipartition, which is again in contradiction to Lemma 2.1. \(\square\)
Claim 5. The vertex \(y_2\) is adjacent to none of \(e_1\), \(x_3\) and \(x_4\) in \(L(G)\).
Proof of Claim 5. This follows from Claim 4 by symmetry. \(\square\)
Claim 6. The vertex \(y_1\) is not adjacent to \(y_2\) in \(L(G)\).
Proof of Claim 6. Suppose that \(y_1\) is adjacent to \(y_2\) in \(L(G)\). There are two possibilities: either \(y_1\) is adjacent to \(x_4\) in \(L(G)\) or it is not.
First, suppose that \(y_1\) is adjacent to \(x_4\) in \(L(G)\). Then by Claims 4 and 5 as well as parts (b) and (c) of Lemma 2.8, we have the following:
\(\circ\) \(y_1 y_2 x_2 x_3 x_4 y_1\) is an induced cycle of length \(5\) in \(L(G)\), provided \(y_2\) is adjacent to \(x_2\) in \(L(G)\);
\(\circ\) \(y_1 y_2 e_2 x_2 x_3 x_4 y_1\) is an induced cycle of length \(6\) in \(L(G)\), provided \(y_2\) is not adjacent to \(x_2\) in \(L(G)\).
Both of the above lead to contradictions, since each of them, together with Lemma 2.6, implies that \(G\) has a cycle of length greater than \(4\).
Now, suppose that \(y_1\) is not adjacent to \(x_4\) in \(L(G)\). Then by Claims 4 and 5 as well as parts (a), (b) and (c) of Lemma 2.8, we have the following:
\(\circ\) \(y_1 y_2 x_2 x_3 x_4 e_1 y_1\) is an induced cycle of length \(6\) in \(L(G)\), provided \(y_2\) is adjacent to \(x_2\) in \(L(G)\);
\(\circ\) \(y_1 y_2 e_2 x_2 x_3 x_4 e_1 y_1\) is an induced cycle of length \(7\) in \(L(G)\), provided \(y_2\) is not adjacent to \(x_2\) in \(L(G)\).
Again, both lead to contradictions, since each of them, together with Lemma 2.6, implies that \(G\) has a cycle of length \(\ge 6\).
Since both possibilities lead to a contradiction, Claim 6 holds true. \(\square\)
Claim 7. The vertex \(y_1\) is not adjacent to \(x_4\) in \(L(G)\).
Proof of Claim 7. Suppose that \(y_1\) is adjacent to \(x_4\) in \(L(G)\). There are two possibilities: either \(y_2\) is adjacent to \(x_2\) in \(L(G)\) or it is not.
First, suppose that \(y_2\) is adjacent to \(x_2\) in \(L(G)\). Then by Claims 1, 4, 5 and 6 as well as Lemma 2.8(c), \(y_1 e y_2 x_2 x_3 x_4 y_1\) is an induced cycle of length \(6\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(6\), a contradiction.
Now, suppose that \(y_2\) is not adjacent to \(x_2\) in \(L(G)\). Then by Claims 1, 4, 5 and 6 as well as parts (b) and (c) of Lemma 2.8, \(y_1 e y_2 e_2 x_2 x_3 x_4 y_1\) is an induced cycle of length \(7\) in \(L(G)\). By Lemma 2.6, this implies that \(G\) has a cycle of length \(7\), again a contradiction.
Since both possibilities lead to a contradiction, Claim 7 holds true. \(\square\)
Now, there are three possibilities: neither of \(y_1\) and \(y_2\) is adjacent to \(x_1\) in \(L(G)\); only one of \(y_1\) and \(y_2\) is adjacent to \(x_1\) in \(L(G)\); or both \(y_1\) and \(y_2\) are adjacent to \(x_1\) in \(L(G)\).
First, suppose that neither of \(y_1\) and \(y_2\) is adjacent to \(x_1\) in \(L(G)\). Then, by Claims 1, 4, 5 and 6 as well as Lemma 2.8(a), \(y_1 e y_2 e_2 x_1 e_1 y_1\) is an induced cycle of length \(6\) in \(L(G)\). This, together with Lemma 2.6, implies that \(G\) has a cycle of length \(6\), a contradiction.
Next, suppose that only one of \(y_1\) and \(y_2\) is adjacent to \(x_1\) in \(L(G)\). Without loss of generality, say \(y_1\) is adjacent to \(x_1\) in \(L(G)\). Then, by Claims 1, 4 and 6, \(y_1 e y_2 e_2 x_1 y_1\) is an induced cycle of length \(5\) in \(L(G)\). Again, by Lemma 2.6, this implies that \(G\) has a cycle of length \(5\), a contradiction.
Finally, suppose that both \(y_1\) and \(y_2\) are adjacent to \(x_1\) in \(L(G)\). Then, by Claims 5, 6 and 7, \(L(G)\) contains a \(K_{1,3}\) as an induced subgraph with \(\{x_1\}\) and \(\{y_1, y_2, x_4\}\) as parts of the bipartition. But this is not possible by Lemma 2.1.
These contradictions tell us that Case III also does not occur.
Since Cases I, II and III all lead to a contradiction, we conclude that \(L(G)^2\) cannot contain the graph \(H\) as an induced subgraph. This completes the proof. \(\square\)
Lemma 2.10. Let \(G\) be a graph containing an induced cycle \(C = x_1 x_2 \ldots x_n x_1\) of length \(n \ge 6\), Then there exist five vertices of \(C\) whose induced subgraph in the complement \(\overline{G}\) is isomorphic to the graph \(H\) shown in Figure 3.
Proof. Let \(C = x_1 x_2 \ldots x_n x_1\) be an induced cycle of \(G\) with \(n \ge 6\). Since \(C\) is induced, vertices \(x_i\) and \(x_j\) are adjacent in \(G\) if and only if \(j \equiv i\pm1 \pmod n\).
Consider the five vertices \(x_1, x_2, x_{n-2}, x_{n-1}, x_n\) of \(C\). Among these vertices, the adjacencies in \(G\) occur only between consecutive vertices in the cycle. Consequently, the nonadjacencies in \(G\), which become edges in the complement \(\overline{G}\), yield exactly the graph \(H\) shown in Figure 3. Hence, \(\overline{G}\) contains \(H\) as an induced subgraph. \(\square\)
We conclude this section by providing a proof of Theorem 1.1 (Theorem A) and adding a remark.
Proof of Theorem 1.1 (Theorem A). We show below that neither \(L(G)^2\) nor \(\overline{L(G)^2}\) contains an induced odd cycle of length at least \(5\). Then it follows from the strong perfect graph theorem that \(L(G)^2\) is perfect; thus completing the proof.
The graph \(L(G)^2\) does not contain any induced odd cycle of length \(n \ge 5\); otherwise, by Lemma 2.5, \(L(G)\) would contain an induced cycle of length \(\ge n \ge 5\). Then it follows from Lemma 2.6 that \(G\) contains a cycle of length \(\ge 5\), which contradicts the assumption.
The graph \(\overline{L(G)^2}\) does not contain any induced odd cycle of length \(n \ge 5\). Indeed, it does not contain any induced cycle of length \(5\), since the complement of an induced cycle of length \(5\) is again an induced cycle of length \(5\). Also, it does not contain any induced cycle of length \(n \ge 7\); otherwise, based on Lemma 2.10, \(L(G)^2\) would contain the graph \(H\), presented in Figure 3, as an induced subgraph, which is in contradiction to Lemma 2.9. \(\square\)
It is worthwhile to note that if the graph \(G\) contains no cycle of length greater than \(4\), then it follows immediately that \(G\) contains no induced cycle of such length. By [19, Lemma 3.2], one may then deduce that \(L(G)^2\) likewise contains no induced cycle of length greater than \(4\). This yields an alternative argument, distinct from the one presented in our proof of Theorem 1.1 (Theorem A), that \(L(G)^2\) contains no induced odd cycle of length \(\ge 5\).
Let \(G\) be a graph. A strong edge-coloring of \(G\) is an assignment of colors to the edges of \(G\) in such a way that no two edges of \(G\) with a common endpoint or with an edge that is adjacent to both of them receive the same color. The strong chromatic index of \(G\), denoted by \({}_{\mathcal{S}} \chi'(G)\), is the minimum number of colors that allow a strong edge-coloring of \(G\). Many open problems that involve the strong edge-coloring of graphs are known to exist and among them, it appears that the problems concerning upper bounds for \({}_{\mathcal{S}} \chi'(G)\) have generated considerable interest. In what follows, we point out some known conjectures about upper bounds for \({}_{\mathcal{S}} \chi'(G)\).
Suppose that \(G\) has maximum degree \(\Delta\), that is, \(\Delta\) is the largest degree among vertices of \(G\). Perhaps the most important conjecture related to upper bounds for \({}_{\mathcal{S}} \chi'(G)\) was proposed by Erdős and Nešetřil (see [7]). They conjectured that \[{}_{\mathcal{S}} \chi'(G) \le \left\{\begin{array}{ll} \frac{5}{4} \Delta^2 & \mbox{if }\Delta\mbox{ is even}, \\[0.5cm] \frac{1}{4} (5\Delta^2-2 \Delta+1) & \mbox{if }\Delta\mbox{ is odd}. \end{array} \right.\]
Note that \(\Delta^2\) is less than or equal to both of the above-mentioned upper bounds. Faudree et al. [8] have in fact suggested \(\Delta ^2\) as a sharper upper bound for \({}_{\mathcal{S}} \chi'(G)\) when \(G\) is bipartite. This was confirmed for the case \(\Delta = 3\) by Steger and Yu [20]. Brualdi and Massey [2] proposed a stronger version of the second conjecture by replacing the upper bound \(\Delta^2\) with \(\Delta_1 \Delta_2\), where \(\Delta_1\) and \(\Delta _2\) are the maximum degrees among vertices in the two parts of the bipartition, respectively. Another generalization of the conjecture by Faudree et al. [8] was given by Mahdian [14]. In order to state this conjecture, let \(C_5\) denote the cycle of length \(5\). A graph is called \(C_5\)-free if it does not contain \(C_5\) as an induced cycle. Note that bipartite graphs and \(4\)-chordal graphs are both \(C_5\)-free. Mahdian [14] conjectured that if \(G\) is \(C_5\)-free, then \({}_{\mathcal{S}} \chi'(G) \le \Delta^2\). These conjectures are still wide open and we refer the reader to [16–18, 20] for some partial answers to them.
Theorem 3.1 (Theorem B) below provides a partial affirmative answer to the conjecture of Faudree et al. [8] and the related conjectures mentioned above. The bound \(S \chi'(G) \le \Delta^{2}\) for bipartite graphs was previously proved by Brualdi and Massey [2, Theorem 2.6] under the assumption that every cycle length of \(G\) is divisible by \(4\). Since graphs with no cycle of length greater than \(4\) satisfy this condition, Theorem 3.1 (Theorem B) applies to a subclass of the graphs considered in [2]. While the earlier result is therefore more general, our proof derives the bound from the fact that \(L(G)^{2}\) is perfect (Theorem 1.1 (Theorem A)), offering a structural perspective in this restricted setting.
Theorem 3.1 (Theorem B). Let \(G\) be a bipartite graph with maximum degree \(\Delta\). If \(G\) does not contain any cycle of length greater than \(4\), then \({}_{\mathcal{S}} \chi'(G) \le \Delta^2\).
We conclude this paper with a short proof of Theorem 3.1 (Theorem B). The proof uses Theorem 1.1 (Theorem A) and a few notions that we introduce as follows. A matching of a graph \(G\) is a set of edges of \(G\), no two of which share a common vertex. An induced matching \(M\) of \(G\) is a matching such that no two edges of \(M\) are joined by an edge of \(G\). A set of vertices of \(G\) is called independent if no two of them are adjacent.
Proof of Theorem 3.1 (Theorem B). Note that a color class in a strong edge coloring of \(G\) is an induced matching of \(G\). By [3, Remark 1], every induced matching in \(G\) is an independent set of vertices in \(L(G)^2\), and conversely. This implies that \({}_{\mathcal{S}} \chi'(G) = \chi(L(G)^2)\). By Theorem 1.1 (Theorem A), \(L(G)^2\) is perfect, that is, \(\chi(L(G)^2) = \omega(L(G)^2)\). Hence, we get \({}_{\mathcal{S}} \chi'(G) = \omega (L(G) ^2)\). But, by [9, Theorem 1], we have \(\omega (L(G)^2) \le\Delta^{2}\), and thus, we obtain that \({}_{\mathcal{S}} \chi'(G) \le \Delta^2\), as required. \(\square\)
The research of Chin and Pournaki was in part supported by a grant from the University of Malaya (UMRG No. RG337-15AFR).