There are a number of variations of proper edge-colourings of graphs with restrictions on the subgraphs induced by two colour classes. Deciding whether a graph has a 3-edge-colouring with no 2-coloured 4-cycle is NP-complete for cubic graphs with chromatic index 3. But for bipartite cubic graphs the problem is solved completely in this paper. Furthermore, the minimum number of 2-coloured 4-cycles in a 3-edge-colouring is determined for any subcubic bipartite multigraph.
In this paper we discuss the possibility of giving graphs and multigraphs proper edge-colourings in which there are no, or few, 2-coloured 4-cycles. The purpose of the paper is to present a full solution to this for the particular case of subcubic bipartite multigraphs (as usual, a multigraph is subcubic if it has maximum degree at most 3, and cubic if all vertices have degree 3).
We are concerned with proper edge-colourings, that is an assignment of colours to the edges of a multigraph so that no two adjacent edges get the same colour. These are well studied, an early result (1964) being that of Vizing [14]: let the chromatic index \(\chi'(G)\) be the minimum number of colours for which a multigraph \(G\) has a proper edge-colouring, and let \(\Delta(G)\) be the maximum degree of \(G\); then \(\chi'(G) \leq \Delta(G) + 1\) for any simple graph (for multigraphs, Vizing’s bound is \(\Delta(G) + p(G)\), where \(p(G)\) is the maximum multiplicity of an edge of \(G\)). Thus, for a cubic simple graph the chromatic index is either 3 or 4; it is, however, NP-complete to decide whether it is one or the other (Holyer 1981, [9]). An even earlier result (1936) due to Kőnig [10] is that a bipartite multigraph \(G\) has \(\chi'(G) = \Delta(G)\); thus a bipartite subcubic multigraph always has an edge-colouring with 3 colours.
A restricted class of proper edge-colourings are those where the edge-coloured graph contains no 2-coloured cycles (such a cycle would necessarily be even), so-called acyclic edge-colourings. This class has received a good deal of attention. The concept is a natural analogue to acyclic vertex-colourings. In 1973, Grünbaum [8] defined both the acyclic chromatic number \(\chi_a(G)\) and the acyclic chromatic index \(\chi_a'(G)\) for a graph \(G\) as the smallest number \(k\) for which \(G\) has an acyclic vertex-colouring and an acyclic edge-colouring, respectively. A multiple edge gives rise to a 2-coloured 2-cycle, so we consider acyclic proper edge-colourings for simple graphs only.
Simple graphs \(G\) with \(\chi'(G) = \Delta(G)\) are called Class 1 graphs. In a regular Class 1 graph with an edge-colouring with \(\Delta(G)\) colours all components of 2-coloured subgraphs are even cycles, so asking for \(\chi_a'(G)\) is like asking what it takes to spoil all these 2-coloured cycles. What can you do with an extra colour or two? Quite a lot, it seems. Fiamčík in 1978 [6], and Alon, Sudakov and Zaks in 2001 [1] conjectured that in fact \(\chi_a'(G) \leq \Delta(G)+2\) for all simple graphs \(G\). The conjecture is known to hold in a number of cases, and it holds for random regular graphs, where – remarkably – \(\chi_a'G) = \Delta(G)+1\) (Alon, Sudakov and Zaks [1], Nešetřil and Wormald [13]). \(K_4\) is an example that 2 extra colours are needed; in fact we have that the acyclic chromatic index of a connected subcubic simple graph is 4 except for \(K_4\) and \(K_{3,3}\) for which it is 5 (Andersen, Máčájova and Mazák 2012 [3] completing work of Fiamcik [7]). It is known to be NP-complete to decide if a subcubic graph has acyclic chromatic index 3 (Alon and Zaks [2]).
Thus it is NP-complete to decide if a subcubic simple graph has chromatic index 3, and this is also NP-complete when restricted to cubic graphs, and it is NP-complete to decide if a subcubic graph has acyclic chromatic index 3 – in this case the cubic graphs cannot have acyclic chromatic index 3. In a companion paper [4] to the present we show that the problem of deciding if a cubic Class 1 graph has an edge-colouring with 3 colours without 2-coloured 4-cycles is also NP-complete. That paper also mentions a number of other variations of edge-colouring with similar restrictions.
Given Kőnig’s theorem it seems natural to ask if cubic and subcubic bipartite multigraphs are more amenable to this question (notice that when only excluding 2-coloured 4-cycles, multigraphs again are interesting). And indeed, they are. In this paper we characterize the subcubic bipartite multigraphs which have an edge-colouring with 3 colours without 2-coloured 4-cycles. And we determine, for any subcubic bipartite multigraph, the minimum number of 2-coloured 4-cycles that an edge-colouring with 3 colours can have.
There are some further reasons for being interested in (the avoidance of) 2-coloured 4-cycles. Edge-coloured graphs have applications in design theory and in scheduling, and in both cases there are situations where 2-coloured 4-cycles play a role, as does the avoidance of them. This has been an inspiration for the present paper and for [4], but we only spend a few words on it here, as the particular case we are investigating in this paper is rather special in relation to these situations.
Latin squares of side \(n\) are equivalent to complete bipartite graphs \(K_{n,n}\) edge-coloured with \(n\) colours, and a 2-coloured 4-cycle in such a graph corresponds to a subsquare of side 2 in the square. Latin squares without subsquares of side 2 are called \(N_2\)-latin squares, and their existence was finally completely determined by Kotzig and Turgeon in 1976 [12]. In edge-colouring terms, their result is:
Theorem 1.1. \(K_{n,n}\) has an edge-colouring with \(n\) colours without \(2\)-coloured \(4\)-cycles if and only if \(2 \neq n \neq 4\).
The exceptional case \(n=2\) is simply a 2-coloured 4-cycle, and for the other exceptional case, \(K_{4,4}\), it is interesting that not even \(K_{3,4}\) has an edge-colouring with 4 colours without 2-coloured 4-cycles.
Before the completion of the full Theorem 1, most of it had been established by Kotzig, Lindner and Rosa in a paper [11] where \(N_2\)-latin squares were applied to construct pairwise disjoint Steiner triple systems.
To illustrate further related work we can mention the following result [5]:
Theorem 1.2. For \(d \geq 4, d \neq 5\), the \(d\)-dimensional cube has an edge-colouring with \(d\) colours such that every \(4\)-cycle gets \(4\) distinct colours.
The 3-dimensional cube – for which the conclusion does not hold – plays a big part in our results in the next sections!
Concerning the relationship between edge-colourings of graphs and latin squares we can add the following remark: In many completion results about partially filled latin squares, edge-colourings of bipartite graphs are used in the proof; in fact, used in a way such that if you would want to avoid subsquares of side 2 in the latin square you should avoid 2-coloured 4-cycles in the edge-colouring.
We inject a remark about avoiding 2-coloured 4-cycles when using 4 colours to edge-colour subcubic bipartite multigraphs. This can always be done (and so the interesting question is indeed the one addressed in this paper, using only 3 colours). In fact, we have the following result for subcubic multigraphs in general, be they bipartite or not:
Theorem 2.1. Let \(G\) be a connected subcubic multigraph. Then \(G\) has an edge-colouring with \(4\) colours such that there is no \(2\)-coloured \(4\)-cycle, except if \(G = K_4\) for which this does not hold.
Proof. The theorem is proved in [4] for simple graphs. Now let \(G\) be a connected subcubic multigraph having at least one multiple edge. If \(G\) has just two vertices, there is nothing to prove. So suppose that this is not the case; then \(G\) cannot have any triple edge. Now let \(G'\) be obtained from \(G\) by deleting one edge from each double edge. Then \(G'\) is a connected, subcubic and simple graph different from \(K_4\). By the result for simple graphs, \(G'\) has an edge-colouring with 4 colours 1, 2, 3, 4, with no 2-coloured 4-cycle; if \(G'\) is a 4-cycle we take this edge-colouring to be the one giving each edge a distinct colour.
We show that all the remaining edges of \(G\) can be coloured one by one without creating a 2-coloured 4-cycle: suppose there is no 2-coloured 4-cycle so far, and that the edge of \(G\) to be added and coloured is \(e\), originally in a double edge with the edge \(e'\) of \(G'\), both having endvertices \(u\) and \(v\), say. Let the colour of \(e'\) be 1. At most one other colour is used at each of \(u\) and \(v\), let 4 be a colour not used at either. Giving \(e\) the colour 4 maintains a proper edge-colouring, and if this does not create a 2-coloured 4-cycle, we have indeed extended the colouring to \(e\). If, on the other hand, a 2-coloured 4-cycle arises with the choice of the colour 4 for \(e\), there must be edges of the same colour, say 2, joining \(u\) to a vertex \(u'\) and \(v\) to \(v'\), where \(u'\) and \(v'\) are joined by an edge of colour 4. In this case the colour 3 is available for \(e\), and it cannot create a 2-coloured 4-cycle, because if \(u'\) and \(v'\) were also joined by an edge of colour 3, that is, by a double edge, then \(G\) could have no further vertices and the graph \(G'\) would be a 4-cycle; but the fact that it has two edges of colour 2 contradicts our assumption in this situation.
This completes the proof of Theorem 2.1. ◻
As mentioned in the introduction, Kőnig’s theorem is that a bipartite multigraph \(G\) has \(\chi'(G) = \Delta(G)\), so any bipartite multigraph with maximum degree at most 3 has an edge-colouring with 3 colours. This section describes our results on such colourings containing no 2-coloured 4-cycle.
We begin with simple graphs. Let \(Q\) denote the (3-dimensional) cube graph, and let \(Q^-\) be \(Q\) with a vertex deleted (all vertices of \(Q\) are similar). See Figure 1. Throughout the paper, we illustrate the bipartiteness of our graphs by using different sizes for the vertices in the two bipartition classes.
These two graphs are examples of simple subcubic bipartite graphs that cannot be 3-edge-coloured without 2-coloured 4-cycles. In fact, we have:
Lemma 3.1. Any edge-colouring of \(Q^-\) with \(3\) colours contains at least one \(2\)-coloured \(4\)-cycle, and any edge-colouring of \(Q\) with \(3\) colours contains two disjoint \(2\)-coloured \(4\)-cycles. There exist \(3\)-edge-colourings of \(Q^-\) with exactly one \(2\)-coloured \(4\)-cycle and of \(Q\) with exactly two \(2\)-coloured \(4\)-cycles.
Proof. Consider a 3-edge-colouring of \(Q\) and assume that \(C\) is a 4-cycle which is not 2-coloured; let its edges have consecutive colours 1, 2, 1 and 3. Then the remaining edges incident with the vertices of \(C\) have colours 3, 3, 2 and 2 respectively, and completion of the edge-colouring forces the edges of colours 2 and 3 to induce two disjoint 4-cycles. If there is no 4-cycle of \(Q\) that is not 2-coloured (and such a colouring exists), then obviously there are two disjoint 2-coloured 4-cycles.
Any 3-edge-colouring of \(Q^-\) has distinct colours missing at the degree 2 vertices and so extends to an edge-colouring of \(Q\). One of the two disjoint 2-coloured 4-cycles in this is intact in \(Q^-\).
Edge-colourings with 3 colours of \(Q^-\) with just one 2-coloured 4-cycle and of \(Q\) with just two are easily devised: For \(Q\), consider two disjoint 4-cycles (for example, the two square cycles in Figure 1) and give all edges joining them the colour 1, and colour the edges of the two cycles with colours 2 and 3 so that no further 2-coloured 4-cycle is created; for \(Q^-\), delete a vertex from this colouring of \(Q\). ◻
We prove in this paper that for simple subcubic bipartite graphs \(Q^-\) is the only obstacle to 3-edge-colourings without 2-coloured 4-cycles, in the following sense:
Theorem 3.2. Let \(G\) be a simple subcubic bipartite graph without \(Q^-\) as a subgraph. Then \(G\) has an edge-colouring with \(3\) colours without \(2\)-coloured \(4\)-cycles.
When we consider multigraphs, we have to introduce three new multigraphs playing parts similar to \(Q^-\) and \(Q\). Let \(C^+\) denote a 4-cycle with an edge replaced by a double edge, and let \(C^d\) and \(C^{++}\) be the other two multigraphs of Figure 2, both having \(C^+\) as a subgraph.
Similarly to Lemma 3.1, but even more obvious, we have the following:
Lemma 3.3. Any edge-colouring of \(C^+\) with \(3\) colours contains exactly one \(2\)-coloured \(4\)-cycle, and any edge-colouring of \(C^d\) or \(C^{++}\) with \(3\) colours contains exactly two \(2\)-coloured \(4\)-cycles.
We then have the following theorem for multigraphs, corresponding to Theorem 3.2, showing that for multigraphs \(C^+\) is the only additional obstacle to 2-coloured 4-cycles:
Theorem 3.4. Let \(G\) be a subcubic bipartite multigraph without \(Q^-\) and \(C^+\) as a subgraph. Then \(G\) has an edge-colouring with \(3\) colours without \(2\)-coloured \(4\)-cycles.
Theorems 3.2 and 3.4 are obvious consequences of our main theorem which will be proved in the next section. It is concerned with not just avoiding 2-coloured 4-cycles, but with 3-edge-colourings containing as few such cycles as possible. For this purpose, we define \(\mathop{\mathrm{int}}(G)\) as the minimum number of 2-coloured 4-cycles in a 3-edge-colouring of a subcubic bipartite multigraph \(G\) (2-coloured 4-cycles are also called intercalates, hence this notation; we shall, however, stick with the more suggestive term 2-coloured 4-cycle). That is, \[\mathop{\mathrm{int}}(G) := \min_{\phi}{\#\{\hbox{2-coloured 4-cycles in $\phi$}\}},\] where \(\phi\) ranges over all proper 3-edge-colourings of \(G\).
Our theorem then states that this minimum depends on the number of obstacles in the multigraph, where the obstacles are \(Q^-\) and \(C^+\) appearing in Theorem 5. It is in fact – except for a few multigraphs – equal to the maximum number of disjoint obstacles. To formulate this explicitly we also need the following notation: for a multigraph \(G\), let
\[\mathop{\mathrm{obs}}(G) :=\max{\{k : \hbox{$G$ has $k$ pairwise disjoint subgraphs each isomorphic to $Q^{-}$ or $C^{+}$}\}}.\]
In any 3-edge-colouring, disjoint obstacles give rise to distinct 2-coloured 4-cycles, so we have that \[\mathop{\mathrm{int}}(G) \geq \mathop{\mathrm{obs}}(G),\] for all subcubic bipartite multigraphs \(G\).
The thing to prove is that these two parameters are in fact equal (bar the exceptions).
The precise statement of the theorem is given in the next section also containing the proof.
Theorem 4.1. Let \(G\) be a connected bipartite multigraph of maximum degree at most \(3\). Then \[\mathop{\mathrm{int}}(G) = \mathop{\mathrm{obs}}(G),\] except if \(G\) is one of the multigraphs \(Q\), \(C^d\) and \(C^{++}\) in which case \(\mathop{\mathrm{int}}(G) = 2\) and \(\mathop{\mathrm{obs}}(G) = 1\).
Before embarking on the proof we prove two lemmas on how obstacles may overlap.
Lemma 4.2. Let \(G\) be a connected subcubic bipartite multigraph, and let \(C_2\) be any \(2\)-cycle of \(G\). Then \(C_2\) is disjoint from any \(Q^-\) in \(G\), and either \(C_2\) is contained in a unique \(C^+\), or it is disjoint from any \(C^+\), or \(G = C^{++}\).
Proof. Let \(G \neq C^{++}\), let \(C_2\) be a 2-cycle of \(G\), and let \(c_1\) be a vertex of \(C_2\) also belonging to a subgraph \(H\) isomorphic to \(Q^-\) or \(C^+\). We prove that \(C_2\) is contained in \(H\), and that \(H= C^+\). Then, as \(G \neq C^{++}\), \(C_2\) is contained in no other \(C^+\).
Since each vertex of \(H\) has degree at least 2, the other vertex \(c_2\) of \(C_2\) must also be in \(H\). Then either both edges joining \(c_1\) and \(c_2\) belong to \(H\), or the vertex \(c_1\) has degree 2 in \(H\). In the former case, \(H = C^+\), as required. In the latter case, both \(c_1\) and \(c_2\) have degree 2 in \(H\), so again \(H = C^+\), this time with \(C_2\) disjoint from the 2-cycle of \(C^+\), implying that \(G = C^{++}\), contradicting the assumption. ◻
Lemma 4.3. Let \(G\) be a connected subcubic bipartite multigraph, and suppose that a vertex \(v\) of \(G\) is contained in two distinct subgraphs \(H_1\) and \(H_2\) of \(G\), where each of \(H_1\) and \(H_2\) is isomorphic to \(C^+\) or \(Q^-\).
Then either both of \(H_1\) and \(H_2\) are isomorphic to \(C^+\) and \(G\) is \(C^{++}\) or \(C^d\), or both \(H_1\) and \(H_2\) are isomorphic to \(Q^-\) and are subgraphs of the same copy of \(Q\), or \(Q\) minus an edge, in \(G\).
Naturally, if there is a copy of \(Q\) in \(G\), then \(G = Q\).
Proof. If \(v\) is contained in a 2-cycle of \(G\), it follows from Lemma 4.2 that \(G = C^{++}\), and \(H_1\) and \(H_2\) are both copies of \(C^+\). Suppose in the following that \(v\) is not on a 2-cycle.
If one of \(H_1\) and \(H_2\), say \(H_1\), is isomorphic to \(C^+\), then \(H_2\) cannot be isomorphic to \(Q^-\), as by Lemma 4.2 such a \(Q^-\) could not contain any vertex from the 2-cycle of \(H_1\) and so would have two neighbouring vertices of degree at most 2. So \(H_2\) is also isomorphic to \(C^+\), and since \(v\) is not on any 2-cycle, \(H_2\) is disjoint from the 2-cycle of \(H_1\) which implies that \(G = C^d\).
Finally, assume that both \(H_1\) and \(H_2\) are isomorphic to \(Q^-\). The vertex \(v\) plays no part in the remaining arguments. In any \(Q^-\), exactly one vertex has the property that itself and all its neighbours have degree 3 in \(Q^-\). Let us call such a vertex central in the \(Q^-\). Each of the other degree 3 vertices of a \(Q^-\) is joined to the central vertex and to two vertices of degree 2. Since \(G\) is bipartite, the vertices of \(H_1\) induce no further edges in \(G\), and so \(H_2\) must contain a vertex not in \(H_1\). Hence there must be an edge of \(H_2\) joining a vertex \(u\) also in \(H_1\) to a vertex \(w\) not in \(H_1\).
If \(u\) has degree 2 in \(H_2\), say the edge \(uu_1\) belongs to both \(H_1\) and \(H_2\), and the edge \(uu_2\) belongs to \(H_1\) but not \(H_2\), then \(u_1 \neq u_2\) and the central vertex \(c_2\) of \(H_2\) is joined to both \(w\) and \(u_1\), and the central vertex \(c_1\) of \(H_1\) is joined to both \(u_2\) and \(u_1\); \(c_1 \neq c_2\), as \(c_2\) is joined to \(w\) and \(c_1\) is not. Further, \(u_1\) has degree 3 in both \(H_1\) and \(H_2\) (being neighbour of a degree 2 vertex in both). It follows that \(c_1\) is in \(H_2\), and it must be a degree 2 vertex there as it is joined to the degree 3 vertex \(u_1\) which is not central in \(H_2\). Then \(c_1u_2\) cannot be in \(H_2\), since \(u_2\) would also be a degree 2 vertex in \(H_2\). It follows that \(u_2\) is not in \(H_2\). Let the third neighbour of \(c_1\) in \(G\) be \(c\). As \(c_1\) has degree 2 in \(H_2\), \(c_1c\) is in \(H_2\), and \(c\) is joined to its central vertex \(c_2\). As \(c\) has degree 3 in both \(H_1\) and \(H_2\), both multigraphs contain its third neighbour \(c'\). So \(H_1\) has vertex set \(\{u,u_1,u_2,c_1,c_2,c,c'\}\) and \(H_2\) vertex set \(\{u,u_1,w,c_1,c_2,c,c'\}\). So \(G\) contains a copy of \(Q\) such that \(H_1 = Q-w\) and \(H_2 = Q-u_2\).
So we may now assume that \(u\) has degree 3 in \(H_2\). If \(u\) is the central vertex of \(H_2\), this immediately forces all vertices of \(H_1\) but one, say \(w'\), to belong to \(H_2\), and we again have a \(Q\) such that \(H_1 = Q-w\) and \(H_2 = Q-w'\). If \(u\) is not central in \(H_2\), but one of its neighbours in \(H_1\) has degree 3 in \(H_2\) and so is central in \(H_2\), we get the same situation, except that possibly the edge \(ww'\) is not in \(G\) which in that case contains a copy of \(Q\) minus an edge. Finally, if both neighbours of \(u\) in \(H_1\) are degree 2 vertices of \(H_2\), then since they cannot have a further joint neighbour in \(H_2\), the central vertex \(c_1\) of \(H_1\) (neighbour of both) cannot be in \(H_2\). It follows that \(G = Q\), \(H_1 = Q – w\) and \(H_2 = Q – c_1\). ◻
We now prove our main result, Theorem 4.1.
Proof. It will be convenient to work with cubic multigraphs only, i.e., to assume that all vertices have degree 3. We show that this will suffice. Assume that the theorem is proved for cubic multigraphs, and let \(G\) be a connected bipartite multigraph with maximum degree at most 3 and with bipartition \((A,B)\) of the vertex set, and having at least one vertex of degree less than 3. We construct a cubic multigraph \(G'\) by “doubling” \(G\): Let \(G_c\) be a copy of \(G\) with bipartition \((A_c,B_c)\) corresponding to \((A,B)\), disjoint from \(G\). Then \(G'\) is obtained from \(G \cup G_c\) by connecting each vertex \(v\) of \(G\) of degree less than 3 to its counterpart in \(G_c\) by a path of length 3, where the middle edge is doubled if \(v\) has degree 2 in \(G\), and both endedges are doubled if \(v\) has degree 1 in \(G\). Note that no edge from these paths is in a 4-cycle of \(G'\), and so the edges of the paths cannot belong to any obstacle in \(G'\). Hence \(\mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G_c) + \mathop{\mathrm{obs}}(G) = 2 \mathop{\mathrm{obs}}(G)\). Then \(G'\) is connected, cubic and bipartite (\(A \cup B_c\) belongs to one bipartition class, \(B \cup A_c\) to the other). And \(G'\) is not \(Q\), \(C^d\) or \(C^{++}\), so as the theorem is assumed to be true for cubic multigraphs, we have that \(\mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G')\). We have that \(\mathop{\mathrm{int}}(G') \geq \mathop{\mathrm{int}}(G_c) + \mathop{\mathrm{int}}(G) = 2 \mathop{\mathrm{int}}(G)\) as any edge-colouring of \(G'\) induces edge-colourings of \(G_c\) and \(G\); and there is a 3-edge-colouring of \(G'\) with \(2 \mathop{\mathrm{int}}(G)\) 2-coloured 4-cycles, because any 3-edge-colouring of \(G\) can be extended to \(G'\) by using the same colouring on \(G_c\) and colouring the edges of the 3-paths in the obvious way (where the endedges get the colours missing from their endvertices in \(G\) and \(G_c\) in the edge-colourings of these multigraphs). So \(\mathop{\mathrm{int}}(G') = 2 \mathop{\mathrm{int}}(G)\). Hence \[2 \mathop{\mathrm{int}}(G) = \mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G') = 2 \mathop{\mathrm{obs}}(G),\] so the theorem holds for \(G\). The assumption that \(G\) contains a vertex of degree less than 3 prevents both \(G\) and \(G'\) from being one of the exceptional multigraphs.
We prove the theorem for cubic multigraphs by induction on the number of vertices of \(G\). The statement about \(Q\), \(C^d\) and \(C^{++}\) follows from Lemmas 3.1 and 3.3 and inspection (although a 3-edge-colouring of \(Q\) with six 2-coloured 4-cycles exists, it can be done with only two, as also stated in Lemma 3.1). If \(G\) has no 4-cycles, then clearly \(\mathop{\mathrm{int}}(G) = 0 = \mathop{\mathrm{obs}}(G)\). This observation also takes care of small values of \(|V(G)|\), i.e., the induction start.
Now assume that \(G\) is a connected
cubic bipartite multigraph,
\(|V(G)| \geq 4\), \(G \not\in \{ Q, C^d, C^{++}\}\), \(G\) has at least one 4-cycle, and \(\mathop{\mathrm{int}}(G') =
\mathop{\mathrm{obs}}(G')\) for all connected cubic bipartite
multigraphs \(G'\), \(G' \not\in \{ Q,
C^d, C^{++}\}\), and \(|V(G')| <
|V(G)|\). We must prove that \(\mathop{\mathrm{int}}(G) =
\mathop{\mathrm{obs}}(G)\). As noted earlier, \(\mathop{\mathrm{int}}(G) \geq
\mathop{\mathrm{obs}}(G)\) always.
We divide the proof into three cases, according to whether \(G\) contains a 3-ladder or a 4-ladder as a subgraph, where an \(l\)-ladder consists of two disjoint paths on \(l\) vertices, say \(u_1, u_2, \ldots, u_l\) and \(v_1, v_2, \ldots, v_l\) respectively (in order along the paths), together with edges \(u_iv_i\) for \(i = 1, 2, \ldots, l\). See Figure 3 for our cases.
Case 1: \(G\) contains no 3-ladder.
Let \(C\) be any 4-cycle of \(G\), with vertices \(c_1,c_2,c_3,c_4\) in order around the cycle. If no vertex of \(C\) has an edge to a vertex not in \(C\), then as \(G\) is bipartite and cubic, we would have \(G = C^{++}\) which is excluded. So we assume that \(G\) has vertices outside \(C\).
Now first assume that \(G\) contains a further edge joining two vertices of \(C\), say that \(c_1\) and \(c_4\) are on a 2-cycle of \(G\). Let \(G'\) be obtained from \(G\) by deleting \(c_1\) and \(c_4\) and adding a further edge between \(c_2\) and \(c_3\), as indicated in Figure 4.
This transition removes the obstacle induced by \(c_1\), \(c_2\), \(c_3\) and \(c_4\). Note that both \(c_2\) and \(c_3\) have neighbours, \(a_2\) and \(a_3\) respectively, outside \(C\) and these are not neighbours, as \(G\) contains no 3-ladder.
Clearly \(G'\) is connected, bipartite and cubic, and since it contains a 2-cycle not belonging to a 4-cycle, it is neither \(Q\), \(C^d\) nor \(C^{++}\). As \(G'\) has fewer vertices than \(G\), by the induction hypothesis \(\mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G')\). In \(G'\), neither \(c_2\) nor \(c_3\) belong to any \(Q^-\), by Lemma 4.2. And \(c_2\) and \(c_3\) do not belong to a \(C^+\) in \(G'\), by the remark above about \(a_2\) and \(a_3\) not being neighbours. It follows that every obstacle in \(G'\) is also in \(G\), and since the \(C^+\) from \(G\) containing \(c_1\) and \(c_4\) is not in \(G'\) we have \(\mathop{\mathrm{obs}}(G) = \mathop{\mathrm{obs}}(G') + 1\).
Now consider a 3-edge-colouring of \(G'\) with \(\mathop{\mathrm{int}}(G')\) 2-coloured 4-cycles. We modify it to an edge-colouring of \(G\) as seen in Figure 5. This produces an edge-colouring of \(G\) with just one additional 2-coloured 4-cycle, and so \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') + 1 = \mathop{\mathrm{obs}}(G') + 1 = \mathop{\mathrm{obs}}(G)\), as required.
For the remainder of Case 1 we assume that \(G\) has no further edge joining two vertices of \(C\), i.e., we assume that \(C\) is an induced subgraph of \(G\). For \(1 \leq i \leq 4\), let the neighbour of \(c_i\) outside \(C\) be \(a_i\) (\(G\) is cubic). Possibly \(a_1= a_3\) or \(a_2 = a_4\) (both cannot happen, as this would imply the existence of a 3-ladder), but no two of the \(a_i\) are neighbours, as \(G\) is bipartite and contains no 3-ladder.
Let \(G'\) be obtained from \(G\) by deleting \(V(C)\) and adding two new vertices \(x\) and \(y\), joining \(x\) to \(a_1\) and \(a_3\), and similarly joining \(y\) to \(a_2\) and \(a_4\), and finally joining \(x\) and \(y\). Figure 6 illustrates this (for the case where \(a_1\) \(,a_2\), \(a_3\) and \(a_4\) are distinct). If \(a_1\) and \(a_3\) are identical, then \(x\) is joined to this vertex by a double edge, and similarly for \(y\) if \(a_2 = a_4\). These possibilities should be kept in mind in the following. Furthermore, it is possible that the transition from \(G\) to \(G'\) will create an additional obstacle, as we shall see.
Then \(G'\) has fewer vertices than \(G\), is connected, bipartite and cubic. And \(G'\) is not \(Q\), \(C^d\) or \(C^{++}\) as the edge \(xy\) is not on any 4-cycle. So, by the induction hypothesis we have that \(\mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G')\).
Consider an edge-colouring of \(G'\) with 3 colours and \(\mathop{\mathrm{int}}(G')\) 2-coloured 4-cycles. We modify it to an edge-colouring of \(G\) with no more 2-coloured 4-cycles as indicated in the two cases of Figure 7.
If, say, \(a_1 = a_3\) both modifications will work. As the \(a_i\) are not neighbours, we get no 2-coloured 4-cycle in \(G\) that is not in \(G'\). So \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G')\). This means that if \(\mathop{\mathrm{obs}}(G') \leq \mathop{\mathrm{obs}}(G)\) we have altogether \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G') \leq \mathop{\mathrm{obs}}(G)\) and are finished. So we consider the possibility that \(\mathop{\mathrm{obs}}(G') > \mathop{\mathrm{obs}}(G)\).
If \(\mathop{\mathrm{obs}}(G') > \mathop{\mathrm{obs}}(G)\), then \(x\) or \(y\) must be in an obstacle in \(G'\), possibly both. But the edge \(xy\) cannot belong to a \(Q^-\) or \(C^+\) as it is not in any 4-cycle. So if \(x\) or \(y\) is in an obstacle, it must be as a degree 2 vertex. Then \(x\) and \(y\) cannot belong to the same \(Q^-\) as all degree 2 vertices of a \(Q^-\) are in the same bipartition class, and \(x\) and \(y\) are in different classes. It follows that if, say, \(x\) belongs to a \(Q^-\) then \(Q^- – x\) is a 3-ladder contained in \(G\), contrary to hypothesis. So we only have to consider \(x\) and \(y\) belonging to a \(C^+\). Suppose first that exactly one of them, say \(x\), belongs to a \(C^+\). We get the situation of Figure 8, shown in both \(G'\) and \(G\). By Lemma 4.3, \(x\) is in just the one \(C^+\) which is not in \(G\), so \(\mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G) + 1\).
Figure 9 shows how a 3-edge-colouring of \(G'\) with \(\mathop{\mathrm{int}}(G')\) 2-coloured 4-cycles may be modified to a 3-edge-colouring of \(G\) with one less 2-coloured 4-cycle (there are two possibilities), so \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') – 1\). Altogether we get \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') -1 = \mathop{\mathrm{obs}}(G') – 1 = \mathop{\mathrm{obs}}(G)\) also in this case.
To finish Case 1, assume that both \(x\) and \(y\) belong to a \(C^+\). Then each is in in exactly one such, and the two are distinct. We get the situation from Figure 10 with relevant edge-colourings indicated (the same colouring in \(G\) can be used for the case where colours 1 and 2 are interchanged in the 4-cycle containing \(a_4ya_2\), as all that matters is that the colour 3 is absent from \(a_2\) and \(a_3\)), and we have \(\mathop{\mathrm{int}}(G) = \mathop{\mathrm{int}}(G') – 2 = \mathop{\mathrm{obs}}(G') – 2 = \mathop{\mathrm{obs}}(G)\).
This finishes Case 1.
Case 2: \(G\) contains a 3-ladder, but no 4-ladder.
Let \(L\) be any 3-ladder of \(G\).
If all four degree 2 vertices of \(L\) have a further edge to a vertex of \(L\), then since \(G\) is bipartite and not \(C^d\), \(G\) must be the graph of Figure 11 for which we have \(\mathop{\mathrm{int}}(G) = \mathop{\mathrm{obs}}(G) = 0\).
Assume next that exactly 2 of vertices of degree 2 in \(L\) are neighbours in \(G\). If they are neighbours in \(L\) as well, let \(a_1\) and \(a_2\) be the neighbours in \(G\) of the remaining two degree 2 vertices of \(L\) (see the first part of Figure 12).
Since \(G\) is bipartite, \(a_1 \neq a_2\), and since \(G\) contains no 4-ladder, \(a_1\) and \(a_2\) are not neighbours. Let \(G'\) be obtained from \(G\) by deleting \(L\) and adding \(P'\), a path of length 3 with the endedges doubled, and joining one endvertex to \(a_1\), the other to \(a_2\). See Figure 12. The transition removes an obstacle present in \(G\).
Now \(G'\) is connected, cubic and bipartite, and not an exceptional multigraph, so by the induction hypothesis \(\mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G')\). Since no vertex of \(P'\) is in a 4-cycle, \(\mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G'-P')\), and we also have \(\mathop{\mathrm{obs}}(G) = \mathop{\mathrm{obs}}(G-V(L)) + 1\). Now consider a 3-edge-colouring of \(G'\) with \(\mathop{\mathrm{int}}(G')\) 2-coloured 4-cycles. Figure 13 shows how to modify it to an edge-colouring of \(G\) with just the one unavoidable additional 2-coloured 4-cycle (remember that \(a_1\) and \(a_2\) are not neighbours). So \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') + 1\), and summing up we have \[\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') + 1 = \mathop{\mathrm{obs}}(G') + 1 = \mathop{\mathrm{obs}}(G' – P') + 1 =\mathop{\mathrm{obs}}(G – V(L)) + 1 = \mathop{\mathrm{obs}}(G),\] as required.
If the two vertices of \(L\) that are neighbours in \(G-E(L)\) are not neighbours in \(L\), we have the situation of Figure 14. The arguments are basically the same as before, but the inequalities are different, and there is no obstacle intersecting \(L\). We get, with the same notation as before:
\[\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G).\]
For the rest of Case 2 assume that \(L\) is an induced subgraph of \(G\). Let the neighbours in \(G-L\) of the degree 2 vertices be \(a_1,a_2,a_3,a_4\) as indicated to the left in Figure 15. Possibly \(a_1 = a_4\) or \(a_2 = a_3\), but not both, as this would imply the existence of a 4-ladder in \(G\). For the same reason, \(a_1\) is not joined to \(a_2\) and \(a_3\) not to \(a_4\). Note that if \(a_1 = a_4\) (say) then \(L\) belongs to a \(Q^-\) in \(G\). Let \(G'\) be obtained from \(G\) by deleting \(L\), adding two disjoint 2-cycles and joining the endvertices of one to \(a_1\) and \(a_3\), those of the other to \(a_2\) and \(a_4\). See Figure 15.
Then \(G'\) is bipartite and cubic, and it has fewer vertices than \(G\). If \(G'\) is connected, this is the multigraph that we shall use for the induction.
So suppose first that \(G'\) is connected. Then it is not \(C^{++}\) or \(Q\). Further, \(G'\) is not \(C^d\) as this would require that \(a_1 = a_4\) and \(a_2 = a_3\) which we have seen is impossible. By the induction hypothesis, \(\mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G')\). Now let \(\delta_{a_1a_3}\) be 1 if \(a_1a_3\) is in \(G\), 0 otherwise. Similarly for \(\delta_{a_2a_4}\). And let \(\delta = 1\) if \(a_1 = a_4\) or \(a_2 = a_3\), and 0 otherwise. If \(\delta = 1\), then \(\delta_{a_1a_3} = \delta_{a_2a_4} = 0\), as otherwise \(G\) would contain a 4-ladder.
Then, by Lemma 4.2, \(\mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G) + \delta_{a_1a_3} + \delta_{a_2a_4}- \delta\), because the only obstacles in \(G'\) but not in \(G\) would have to intersect the added 2-cycles, and any obstacle in \(G\) but not \(G'\) would have to be a \(Q^-\) intersecting \(L\), and as \(G\) contains no 4-ladder and hence no \(Q\) minus an edge, there can be only one such \(Q^-\), and it occurs if and only if \(\delta = 1\).
Now consider a 3-edge-colouring of \(G'\) with \(\mathop{\mathrm{int}}(G')\) 2-coloured 4-cycles. There are two possibilities for its behaviour on the added 3-paths, and Figure 16 illustrates how to obtain 3-edge-colourings of \(G\) from them, showing that \[\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') – \delta_{a_1a_3} – \delta_{a_2a_4} + \delta.\]
The latter case in Figure 16 cannot occur if \(\delta = 1\). Altogether we then have \[\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{obs}}(G') – \delta_{a_1a_3} – \delta_{a_2a_4} + \delta = \mathop{\mathrm{obs}}(G),\] as desired.
Assume next that \(G'\) as constructed above is not connected. Then it has exactly two connected components (and so has \(G – L\), since a subcubic bipartite multigraph cannot have just one vertex of degree 2). Rather than the 3-paths in the earlier case we now insert 5-paths with two double edges in each and call the resulting two components \(G_1'\) and \(G_2'\). Each is cubic, connected and bipartite, distinct from \(Q\), \(C^d\) and \(C^{++}\), and has fewer vertices than \(G\). So we can use the induction hypothesis on both. Choosing, in both components, 1 as the colour occurring thrice on the 5-paths, with the edge-colouring modification of the lower right multigraph in Figure 16 we get \[\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G_1') + \mathop{\mathrm{int}}(G_2') = \mathop{\mathrm{obs}}(G_1') + \mathop{\mathrm{obs}}(G_2') = \mathop{\mathrm{obs}}(G),\] noting that in this case \(L\) intersects no obstacle in \(G\).
This completes Case 2.
Case 3: \(G\) contains a 4-ladder.
We wish to find a 4-ladder for which the two degree 2 vertices \(c_1\) and \(c_2\) (see Figure 17) do not have additional neighbours \(a_1\) and \(a_2\) outside the 4-ladder for which \(a_1a_2\) belongs to \(G\). We do this by letting \(L_l\) be a longest ladder in \(G\) and choose \(L\) from one end of \(L_l\). Then \(c_1\) and \(c_2\) will have the desired property unless they are joined to the degree 2 vertices at the other end of \(L_l\), so that \(L_l\) and these edges are the whole of \(G\). In this special case, since \(G \neq Q\) it can be given a 3-edge-colouring without 2-coloured 4-cycles by giving both \(c_1c_2\) and the opposite edge in the 4-cycle of \(L\) containing \(c_1c_2\) the colour 3, giving the remaining two edges in this 4-cycle distinct colours 1 and 2, and continuing as forced, and so \(\mathop{\mathrm{int}}(G) = \mathop{\mathrm{obs}}(G) = 0\) (all “vertical” edges will get the colour 3, and the edges of colours 1 or 2 will span one or two even cycles).
So assume now that \(L\) is a 4-ladder in \(G\) which cannot be extended with neighbours of \(c_1\) and \(c_2\). If all degree 2 vertices of \(L\) have their third neighbour in \(L\) as well, then since \(G\) is bipartite and not the cube, it is the graph of Figure 18, for which \(\mathop{\mathrm{int}}(G) = \mathop{\mathrm{obs}}(G) = 2\).
If exactly two of the degree 2 vertices of \(L\) are joined to vertices of \(G\) outside \(L\) (one in each bipartition class), let their neighbours not in \(L\) be \(u\) and \(v\), and let \(G'\) be obtained from \(G\) by deleting \(V(L)\) and adding a 3-path with its endedges doubled and joining its endvertices to \(u\) and \(v\), as before. The graph \(G'\) has fewer vertices than \(G\) and is connected, cubic and bipartite, and it is not an exceptional graph. So we can use the induction hypothesis on \(G'\). A 3-edge-colouring of \(G'\) with \(\mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G')\) 2-coloured 4-cycles can be modified to one of \(G\) as illustrated for the three possible cases in Figure 19. Here we assume that 1 is the colour of the middle edge of the 3-path (and hence the colour of the edges to \(u\) and \(v\)), and we use symmetry to restrict to three cases.
In case a), if \(u\) and \(v\) are joined by a double edge then \(G\) has just these 10 vertices and \(\mathop{\mathrm{int}}(G) = \mathop{\mathrm{obs}}(G) = 2\). Otherwise, the colour of \(c_3c_4\) is chosen distinct from the colour of a possible edge \(uv\), and so \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') + 1 = \mathop{\mathrm{obs}}(G') + 1 = \mathop{\mathrm{obs}}(G)\); the same inequality holds in case b) where there can be no \(uv\)-edge.
In case c), \(G\) contains a cube minus an edge, not in \(G'\). This contains two \(Q^-\) (obviously not disjoint), so \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') + 1 = \mathop{\mathrm{obs}}(G') +1 = \mathop{\mathrm{obs}}(G)\).
So assume for the rest of Case 3 that \(L\) is an induced subgraph of \(G\). Let the neighbours outside of \(L\) be \(a_1,a_2,a_3,a_4\) as before. There is no edge between \(a_1\) and \(a_2\), but possibly between \(a_3\) and \(a_4\); also possibly \(a_4 = a_2\) or \(a_1 = a_3\) or both. Let \(G'\) be obtained from \(G\) by deleting \(L\) and adding a 6-vertex graph (a 5-path with the endedges doubled) with its degree 2 vertices joined to \(a_1, a_2, a_3,a_4\) as indicated in Figure 20.
Figure 21 shows how to modify an edge-colouring of \(G'\) with \(\mathop{\mathrm{int}}(G')\) 2-coloured 4-cycles to an edge-colouring of \(G\). If \(a_4 \neq a_2\) and \(a_1 \neq a_3\), these two edge-colourings have the same number of 2-coloured 4-cycles (remember that there is no edge in \(G\) joining \(a_1\) and \(a_2\)), so \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G')\). So altogether in this case \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') = \mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G)\) as required.
If, say \(a_4 = a_2\) and \(a_1 \neq a_3\), then \(G'\) has an obstacle, containing \(a_4\), not in \(G\), and so \(\mathop{\mathrm{obs}}(G') = \mathop{\mathrm{obs}}(G)+1\), but the corresponding 2-coloured 4-cycle is not in \(G\) either, and so \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') – 1\). Thus we have, in this case, \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') – 1 = \mathop{\mathrm{obs}}(G') -1 = \mathop{\mathrm{obs}}(G)\), as desired.
And finally, if both \(a_4 = a_2\) and \(a_1 = a_3\) there are two obstacles in \(G'\) not in \(G\), and also two 2-coloured 4-cycles in the edge-coloured \(G'\) not in the edge-coloured \(G\), so we get \(\mathop{\mathrm{int}}(G) \leq \mathop{\mathrm{int}}(G') – 2 = \mathop{\mathrm{obs}}(G') – 2 = \mathop{\mathrm{obs}}(G)\).
This completes the proof of Theorem 4.1. ◻
The authors wish to thank an anonymous referee for a very thorough reading of the manuscript and several helpful suggestions.