betaFeedback

WorksMathematics

Strong edge-colourings of truncations of cubic graphs

Abstract

We study a problem posed by Kardoš asking whether the truncation of every connected simple bridgeless cubic graph has strong chromatic index six. The truncation T(G)T(G) is obtained by replacing each vertex of a graph GG with a triangle and attaching its three incident edges to distinct vertices of that triangle. Han and Cui established an affirmative answer for prism bases. We prove that the strong chromatic index is six whenever GG is a connected simple cubic graph that is bipartite or is both bridgeless and claw-free. Both proofs are constructive and use a common compatibility criterion for combining colourings of smaller pieces. The same equality holds for connected loopless cubic multigraphs in either class, with the sole exception of the 33-bond, whose truncation is the triangular prism and has strong chromatic index nine.

Introduction

All graphs considered in this paper are finite and non-empty. Undirected graphs are loopless and are simple unless stated otherwise. Throughout the paper, base graphs are assumed to be connected unless explicitly stated otherwise. For standard graph-theoretic terminology we refer to Bondy and Murty [2]. In multigraphs we distinguish parallel edges and their incidences; two parallel edges form a cycle of length two. We write ∂G(v)\partial_G(v) for the set of edges incident with vv and δG(S)\delta_G(S) for the edge cut determined by S⊆V(G)S \subseteq V(G). The term kk-connected refers to vertex connectivity.

Two distinct edges are in strong conflict if they are adjacent or are both adjacent to a common edge. A strong edge-colouring of GG assigns distinct colours to edges in strong conflict. For simple graphs, this is equivalent to requiring each colour class to be an induced matching. The minimum number of colours in such a colouring is the strong chromatic index of GG, denoted by χs′(G)\chi'_s(G).

Strong edge-colourings were introduced by Fouquet and Jolivet in 1983 [6]. A central problem is to bound the strong chromatic index in terms of the maximum degree. In 1985, Erdős and Nešetřil conjectured that every graph of maximum degree Δ\Delta has strong chromatic index at most 5Δ2/45\Delta^2/4; see [5]. For subcubic graphs, Andersen [1] and, independently, Horák, He Qinq and Trotter [10] established the sharp upper bound of ten colours.

Smaller bounds become possible when additional structure is imposed. The claw-free case is particularly relevant here. A claw is a graph isomorphic to K1,3K_{1,3}, and a diamond is a graph isomorphic to K4K_4 with one edge deleted. The two nonadjacent vertices of a diamond are its tips. A graph is claw-free or diamond-free if it has no induced claw or induced diamond, respectively. For a multigraph, claw-freeness refers to its underlying simple graph.

In 2022, Lv, Li and Zhang [14] proved that every connected claw-free subcubic graph other than the triangular prism admits a strong edge-colouring with at most eight colours. Lin and Lin [13] subsequently improved this bound to seven and constructed an infinite family attaining it. These results motivate the study of more restricted classes in which six colours might suffice.

One such class is provided by truncations. Let GG be a loopless cubic multigraph. Its truncation T(G)T(G) has a vertex (v,e)(v,e) for each incidence of a vertex vv with an edge ee. The three vertices associated with vv induce a triangle Δv\Delta_v, called a canonical triangle. For every edge e=uve=uv of GG, the graph T(G)T(G) has the edge (u,e)(v,e)(u,e)(v,e). Edges within canonical triangles are called internal, and the edges corresponding to E(G)E(G) are called external. The vertex (v,e)(v,e) is the port of ee at vv. In particular, parallel edges of GG have distinct ports, and T(G)T(G) is a simple cubic graph that is both claw-free and diamond-free.

Han and Cui [9] proved that truncations of the prisms Cn□K2C_n \mathbin{\Box} K_2, for every n≥3n \ge3, admit strong edge-colourings with six colours. At the 33rd Workshop on Cycles and Colourings in 2025, Kardoš [11 Problem 4.1] asked whether six colours suffice for every diamond-free claw-free cubic graph, also formulating the question for truncations of cubic graphs. Kardoš subsequently clarified in a private communication [12] that the intended formulation includes the hypothesis of bridgelessness. For simple bases, this leads to the following question:

Does every connected simple bridgeless cubic graph GG satisfy χs′(T(G))=6\chi'_s(T(G)) = 6?

Even when the graph to be coloured is simple, its base need not be: contracting two disjoint triangles joined by more than one edge produces parallel edges. There is then one unavoidable exception. Let M0M_0 denote the 3-bond, the multigraph consisting of two vertices joined by three parallel edges. Its truncation is the triangular prism. All nine edges of the prism are pairwise in strong conflict, so χs′(T(M0))=9\chi'_s(T(M_0)) = 9.

Tanwar [17] constructed an 18-vertex diamond-free claw-free cubic graph with strong chromatic index seven.1 His graph has a bridge, and its triangle contraction has parallel edges. It therefore does not refute the bridgeless version of the problem, nor the version restricted to simple cubic bases.

We prove the following two cases of the question, allowing parallel edges in the base.

Theorem 1.1. Let GG be a connected loopless cubic bipartite multigraph other than M0M_0. Then χs′(T(G))=6\chi'_s(T(G)) = 6.

Theorem 1.2. Let GG be a connected loopless bridgeless cubic claw-free multigraph other than M0M_0. Then χs′(T(G))=6\chi'_s(T(G)) = 6.

Six is a local lower bound: the three edges of a canonical triangle and the three external edges incident with it must all receive different colours. To attain it, we record at each port the colour of its external edge and the two colours exposed at that port. Section 2 determines when two such records are compatible. It also explains why a single pair of parallel edges is the difficult case in a replacement: it forces different colours at its two outside ports, whereas one ordinary edge has the same colour at both ends.

Section 3 proves the bipartite theorem. When perfect matchings of both signs occur, a binary assignment on one partition set gives a colouring directly, even with parallel edges. When all signs agree, the same local rule allows a piece to replace a single vertex. For simple bases, Heawood vertex-sums and 2-edge cuts then complete the proof. This simple-base theorem is also needed for the general case: it forces a smallest counterexample to have parallel edges. Suppressing their blocks gives a simple core in which certain edges are marked. The signs of the perfect matchings restrict those marks, leaving two local replacements to check.

Section 4 gives a single proof for claw-free bases. Its decomposition puts each vertex in a triangle, a diamond or a parallel-edge block, apart from the exceptional base K4K_4 which is treated directly. Where triangle blocks remain, the graph obtained by suppressing the intervening chains is a truncation T(Q)T(Q). Colouring its triangle pieces and restoring the chains gives the desired colouring of T(G)T(G). The same construction yields the double-truncation corollary, which does not require QQ to be bridgeless.

Local colourings and replacements

The proofs of Theorems 1.1 and 1.2 both build a colouring by joining smaller pieces. We first identify the boundary data needed for gluing and then determine how two parallel edges constrain the colours at their outside ports.

Local states and gluing

Let GG be a loopless cubic multigraph. The three edges of any canonical triangle Δv\Delta_v and the three external edges incident with its ports are pairwise in strong conflict. Consequently,

χs′(T(G))≥6.(1)\chi'_s(T(G)) \ge6. \tag*{(1)}

To attain this bound, the six edges around each canonical triangle must use all six colours. The problem is therefore to choose these local assignments so that they remain compatible across external edges.

Fix a set Ω\Omega of six colours. The labels of these colours may vary between constructions. A local state at vv assigns distinct colours to the three internal edges of Δv\Delta_v and its three incident external edges. Write cv(e)c_v(e) for the external colour at the port of e∈∂G(v)e \in\partial_G(v). Let IvI_v be the set of internal colours, the complement in Ω\Omega of the three external colours. For e∈∂G(v)e \in\partial_G(v), let hv(e)h_v(e) be the colour of the internal edge opposite the port (v,e)(v,e). Thus cvc_v and hvh_v map ∂G(v)\partial_G(v) bijectively onto the external and internal colour sets, respectively. The two colours on internal edges incident with (v,e)(v,e) forms its exposed pair

Pv(e)=Iv∖{hv(e)}.P_v(e)=I_v\setminus\{h_v(e)\}.

The pair (cv(e),Pv(e))(c_v(e),P_v(e)) is the signature at this port. These two pieces of information determine whether the port can be joined to a second port. With the ports ordered as (e0,e1,e2)(e_0,e_1,e_2), we write the state as (c0,c1,c2;h0,h1,h2)(c_0,c_1,c_2;h_0,h_1,h_2), where ci=cv(ei)c_i=c_v(e_i) and hi=hv(ei)h_i=h_v(e_i). Thus the entries before the semicolon are the external colours, and those after it are the colours opposite the corresponding ports. In a simple base, a port order may be specified by listing the neighbours. With parallel edges, we use edge labels whenever needed to distinguish the incidences.

Later we will replace a vertex or an edge by a larger coloured piece. To describe the boundary of such a piece, we use cubic poles: loopless multigraphs with dangling half-edges in which every retained vertex has three incidences, counting half-edges. A dangling incidence is called a port of the pole.

The augmented truncation of a pole replaces each retained vertex by its incidence triangle, keeps the ordinary external edges, and replaces each dangling half-edge by a pendant edge to a distinct new degree-1 vertex. These auxiliary degree-1 vertices are not truncated. A strong colouring of a pole means a strong colouring of this augmented truncation. The signature at a port of the pole is measured at the corresponding retained endpoint in the augmented truncation.

Joining two dangling half-edges at the base level replaces them by one ordinary edge. In the augmented truncations, this deletes the two auxiliary endpoints and replaces their pendant edges by one external edge joining the retained ports. The operation may join ports of the same pole or of different poles, provided that the resulting base is loopless and cubic. The following criterion expresses compatibility entirely in terms of these signatures.

Lemma 2.1. Let GG be a loopless cubic multigraph, let Ω\Omega be a set of six colours, and let (cv,hv)(c_v,h_v) be a local state at each vertex v∈V(G)v\in V(G). These states define a strong edge-colouring of T(G)T(G) with colour set Ω\Omega if and only if, for every edge e=uv∈E(G)e=uv\in E(G),

cu(e)=cv(e),Pu(e)∩Pv(e)=∅.(2)c_u(e)=c_v(e),\qquad P_u(e)\cap P_v(e)=\varnothing. \tag*{(2)}

Equivalently, let c:E(G)→Ωc:E(G)\to\Omega be a proper edge-colouring and, for each v∈V(G)v\in V(G), let hv:∂G(v)→Ivh_v:\partial_G(v)\to I_v be a bijection, where Iv=Ω∖{c(f):f∈∂G(v)}I_v=\Omega\setminus\{c(f):f\in\partial_G(v)\}. The assignments cc and (hv)v∈V(G)(h_v)_{v\in V(G)} define a strong edge-colouring of T(G)T(G) if and only if

Iu∩Iv⊆{hu(e),hv(e)}(e=uv).(3)I_u\cap I_v\subseteq\{h_u(e),h_v(e)\}\qquad(e=uv). \tag*{(3)}

For the augmented truncation of a cubic pole, the same criterion applies to its ordinary edges. A dangling edge imposes only the local 6-colour condition at its retained endpoint.

Proof. Suppose first that the local states define a strong edge-colouring. For each base edge e=uve=uv, the corresponding external edge has the same colour at both ends, so cu(e)=cv(e)c_u(e)=c_v(e). It joins the ports (u,e)(u,e) and (v,e)(v,e), so every internal edge incident with the first is in strong conflict with every internal edge incident with the second. Thus Pu(e)∩Pv(e)=∅P_u(e)\cap P_v(e)=\varnothing, proving necessity.

Conversely, suppose that (2.2) holds for every base edge. Equality of the external colours makes the colouring well-defined. Two external edges in strong conflict have ports in the same canonical triangle, and an external edge conflicts with internal edges only in its two endpoint triangles. These conflicts, as well as those between internal edges in the same triangle, are covered by the local 6-colour states. Two internal edges in distinct canonical triangles can be in strong conflict only if an external edge joins an endpoint of one to an endpoint of the other. Their colours then belong to the two exposed pairs at that interface, which are disjoint by (2.2). Thus every pair of edges in strong conflict receives distinct colours, proving sufficiency.

The equivalent formulation (2.3) follows from

Pu(e)∩Pv(e)=(Iu∩Iv)∖{hu(e),hv(e)}.P_u(e)\cap P_v(e)=(I_u\cap I_v)\setminus\{h_u(e),h_v(e)\}.

For a pole, the auxiliary pendant endpoints introduce no internal edges, so the same description applies; each dangling edge is covered by the local state at its retained endpoint. □\square

In particular, one coloured piece may replace another whenever the signatures agree at corresponding boundary ports of the two pieces. This preserves compatibility with the rest of the graph.

Figure 1 records the boundary data at an external edge.

Boundary data at an external edge corresponding to $e=uv$

Figure 1. The boundary data at an external edge corresponding to e=uve=uv. The exposed pairs are U={α1,α2}U=\{\alpha_1,\alpha_2\} and V={β1,β2}V=\{\beta_1,\beta_2\}. Their disjointness is the compatibility condition. The opposite internal colours are hu(e)h_u(e) and hv(e)h_v(e).

The interface criterion gives a gluing rule for two coloured truncations. In the bipartite proof we use it to rejoin the two sides of a 2-edge cut; in the claw-free proof we use it to insert a chain of blocks while preserving the colouring on the rest of the graph.

Lemma 2.2. Let PP and RR be disjoint loopless cubic multigraphs, and suppose that both T(P)T(P) and T(R)T(R) admit strong 6-edge-colourings. Choose edges e=uv∈E(P)e=uv\in E(P) and f=xy∈E(R)f=xy\in E(R), and let GG be obtained from P⊔RP\sqcup R by deleting e,fe,f and adding uy,xvuy,xv. Then T(G)T(G) admits a strong 6-edge-colouring. Given colourings of T(P)T(P) and T(R)T(R), the construction may keep the local states on PP fixed and apply a single permutation of the six colours to those on RR.

Proof. Let cc be the external colour at ee, and let U,VU,V be its exposed pairs at u,vu,v. These are disjoint 2-element sets avoiding cc. Hence {c},U,V\{c\},U,V and the remaining singleton partition the six colours. Denote the corresponding data at ff by d,X,Yd,X,Y, where XX is exposed at xx and YY at yy.

Permute the colours of T(R)T(R) so that dd maps to cc, XX to UU, YY to VV, and the remaining colour to the remaining colour. Assign cc to both new external edges. On uyuy the exposed pairs are U,VU,V, and on xvxv they are again U,VU,V. The two new interfaces are therefore compatible. All local states agree with those in T(P)T(P) and the relabelled T(R)T(R), so Lemma 2.1 applies.

Parallel-edge blocks

The parallel-edge block BB is the 2-pole consisting of two vertices joined by two parallel edges, with one dangling half-edge at each vertex. The following rule determines which signatures can occur together at the two outside ports.

Proposition 2.3. The boundary signatures realised by BB are exactly

(c,W), (d,W),c≠d,∣W∣=2,W∩{c,d}=∅.(4)(c,W),\ (d,W),\qquad c\ne d,\quad|W|=2,\quad W\cap\{c,d\}=\varnothing. \tag*{(4)}

Proof. Write W={r,s}W=\{r,s\} and Ω={c,d,a,b,r,s}\Omega=\{c,d,a,b,r,s\}. In the port order outside, first parallel edge, second parallel edge, the states

(c,a,b;d,r,s),(d,a,b;c,s,r)(c,a,b;d,r,s),\qquad(d,a,b;c,s,r)

give the required signatures and compatible parallel interfaces. Conversely, let a,ba,b be the parallel-edge colours. Equal outside colours would give identical three-element internal palettes, whose exposed two-element pairs cannot be disjoint. Thus the outside colours c,dc,d are distinct, and a,b,c,da,b,c,d are four distinct colours. The internal palettes are {d,r,s}\{d,r,s\} and {c,r,s}\{c,r,s\}. At each parallel interface, its two opposite colours must cover both r,sr,s. Since opposite colours at different ports of a vertex are distinct, each vertex uses r,sr,s opposite its parallel ports. Its boundary exposed pair is consequently {r,s}\{r,s\}, as required.

Joining copies of BB in a cycle gives the boundary prescriptions that we shall also use for bipartite 2-poles. The closure of a single copy is M0M_0, so we start with two copies.

Proposition 2.4. If GG is a cyclic arrangement of k≥2k\ge2 copies of BB, then χs′(T(G))=6\chi'_s(T(G))=6.

Proof. Number the blocks B1,…,BkB_1,\ldots,B_k in cyclic order and let eie_i join BiB_i to Bi+1B_{i+1}, with indices modulo kk. Take U={1,2}U=\{1,2\}, V={3,4}V=\{3,4\} and Z={5,6}Z=\{5,6\} as exposed pairs. For even kk, alternate U,VU,V around the cycle and colour the joins alternately 5,65,6. For odd kk, alternate U,VU,V on B1,…,Bk−1B_1,\ldots,B_{k-1} and assign ZZ to BkB_k. Colour e1,…,ek−2e_1,\ldots,e_{k-2} alternately 5, 6, starting with 5, and give ek−1,eke_{k-1},e_k colours 1, 3, respectively. Thus the two joins at each block have different colours outside its exposed pair, as required by Proposition 2.3. Consecutive blocks expose disjoint pairs, so all joins are compatible. The lower bound (2.1) gives equality.

Bipartite cubic multigraphs

Let GG be a connected loopless cubic bipartite multigraph with partition sets AA and BB. The proof of Theorem 1.1 starts with the signs of the perfect matchings of GG. If both signs occur, a binary assignment on AA gives a colouring of T(G)T(G) directly. If all signs agree, deleting one vertex gives a piece that can replace a vertex in another coloured truncation. We use this replacement first to settle the simple case. A minimum counterexample would then have parallel edges; the final part of the proof shows how to reduce it to a smaller base and restore the colouring.

Matching signs and the colouring formula

Since GG is cubic and bipartite, ∣A∣=∣B∣|A|=|B| and Hall’s theorem [8] guarantees a perfect matching. Fix such a matching. Its complement is a union of even cycles, possibly of length two. Colouring the matching edges with one colour and alternating two further colours on these cycles gives a proper edge-colouring

τ:E(G)⟶{0,1,2}.\tau:E(G)\longrightarrow\{0,1,2\}.

We call the values of τ\tau types. Even when two edges have the same endpoints, their types distinguish their ports. The type will form the first coordinate of each colour. The second coordinate will be a bit assigned to vertices in AA.

Fix orders on AA and BB. A perfect matching MM determines a bijection A→BA\to B, whose sign is denoted by sgn⁡(M)\operatorname{sgn}(M). Changing the orders multiplies all matching signs by the same constant. Replacing a matching edge by a parallel edge preserves the bijection and its sign.

Definition 3.1. Let GG be a bipartite multigraph with a perfect matching, and fix linear orders on its two partition sets. We call GG det-extremal if all its perfect matchings have the same sign.

This property is independent of the orders. Let BGB_G be the biadjacency matrix, whose entries count edge multiplicities. The permanent counts all perfect matchings, while the determinant counts the same matchings with their signs. Thus GG is det-extremal if and only if ∣det⁡BG∣=per⁡BG|\det B_G|=\operatorname{per}B_G; see [7] for simple graphs.

Lemma 3.2. Let GG be a bipartite multigraph with a perfect matching MM, and let CC be an MM-alternating cycle of length 2ℓ2\ell. Then

sgn⁡(M△E(C))=(−1)ℓ−1sgn⁡(M).\operatorname{sgn}\left(M\mathbin{\triangle}E(C)\right)=(-1)^{\ell-1}\operatorname{sgn}(M).

Here △\triangle denotes symmetric difference. Moreover, GG is not det-extremal if and only if some perfect matching of GG admits an alternating cycle whose length is divisible by four.

Proof. Switching along CC induces an ℓ\ell-cycle on the matched images of A∩V(C)A\cap V(C), so the matching sign is multiplied by (−1)ℓ−1(-1)^{\ell-1}. For ℓ=1\ell=1 the switch exchanges parallel edges and leaves the sign unchanged. A cycle of length divisible by four reverses the sign. Conversely, the symmetric difference of two perfect matchings of opposite signs is a union of alternating cycles whose sign changes have negative product. One of these cycles therefore has length divisible by four.

To construct the bits, we contract a perfect matching and retain the direction from AA to BB on the remaining edges. Alternating cycles become directed cycles of half the length, so a cycle witnessing non-det-extremality becomes even. We can alternate the bits around this cycle and then extend the assignment to the remaining vertices.

Lemma 3.3. Let GG be a connected loopless cubic bipartite multigraph with partition sets AA and BB, and let M={aibi:i∈I}M=\{a_i b_i:i\in I\} be a perfect matching, where ai∈Aa_i\in A and bi∈Bb_i\in B. Let DMD_M be the digraph with vertex set II and an arc i→ji\to j for every edge aibj∈E(G)∖Ma_i b_j\in E(G)\setminus M. Then DMD_M is strongly connected. Contracting the edges of MM induces a correspondence between MM-alternating cycles of length 2ℓ2\ell in GG and directed cycles of length ℓ\ell in DMD_M.

Proof. Every vertex of DMD_M has indegree and outdegree two, and its underlying graph is connected. A source strongly connected component has no outgoing arcs by degree balance, so it must contain every vertex.

A directed cycle i0i1⋯iℓ−1i0i_0i_1\cdots i_{\ell-1}i_0 expands to the alternating cycle with edges aitbit+1a_{i_t}b_{i_{t+1}} and bitaitb_{i_t}a_{i_t}, with indices modulo ℓ\ell. Conversely, contracting the matching edges of an alternating cycle gives a directed cycle, oriented by its nonmatching edges from AA to BB. Parallel arcs are kept distinct. A loop represents an alternating 2-cycle; a pair of opposite arcs between distinct vertices represents an alternating 4-cycle.

The condition needed by the colouring formula is that every vertex in BB sees both bits. For simple graphs the equivalence below is the bipartite formulation of [4 Theorem 3.5]. Indeed, take AA as the vertex set of a hypergraph and the neighbourhoods NG(b)N_G(b), indexed by b∈Bb \in B, as its hyperedges. Its incidence graph is GG, and a 2-colouring of this hypergraph is exactly the required bit assignment. The following constructive proof also allows parallel edges.

Lemma 3.4. Let GG be a connected loopless cubic bipartite multigraph with partition sets AA and BB. Then GG is not det-extremal if and only if there exists a map s:A→{0,1}s:A \to\{0,1\} such that

s(NG(b))={0,1}for every b∈B.s(N_G(b)) = \{0,1\} \qquad\text{for every } b \in B.

Proof. Suppose that GG is not det-extremal. By Lemma 3.2, choose a perfect matching MM and an MM-alternating cycle whose length is divisible by four. We construct ss from these data. By Lemma 3.3, the corresponding cycle in DMD_M has even length. Assign alternating bits s(ai)s(a_i) to its vertices ii. Whenever an arc i→ji \to j has an assigned tail and an unassigned head, extend the assignment by setting s(aj)=1−s(ai)s(a_j)=1-s(a_i). Strong connectivity guarantees that this procedure reaches all vertices. Each vertex jj has a predecessor ii on the initial cycle or in this extension with s(ai)≠s(aj)s(a_i) \ne s(a_j). Since both aia_i and aja_j are neighbours of bjb_j, every neighbourhood in BB contains both bits.

Conversely, fix a perfect matching MM. For each jj, choose an incoming arc i→ji \to j such that s(ai)≠s(aj)s(a_i) \ne s(a_j); such an arc exists because aj∈NG(bj)a_j \in N_G(b_j) and this neighbourhood contains both bits. The chosen arcs form a spanning digraph of indegree one, which contains a directed cycle. The bits alternate on that cycle, so its length is even. Lemmas 3.3 and 3.2 imply that GG is not det-extremal.

Use the colour set

Ω={(i,t):i∈{0,1,2}, t∈{0,1}}\Omega= \{(i,t): i \in\{0,1,2\},\ t \in\{0,1\}\}

and index the ports at each vertex by their types. Thus cv(i)c_v(i) is the external colour at the type-ii port, hv(i)h_v(i) is the colour of the opposite internal edge, and Pv(i)={hv(j):j≠i}P_v(i)=\{h_v(j):j\ne i\}. At each vertex, complement the bit in each external colour to obtain the internal palette. To ensure compatibility, place these colours opposite ports of the same type at vertices in AA. At a vertex in BB, start with this placement and swap the colours opposite the two ports whose external colours carry the majority bit. This places each colour shared by adjacent internal palettes opposite their connecting edge at one or both endpoints.

Lemma 3.5. Let GG be a connected loopless cubic bipartite multigraph with partition sets AA and BB, let τ:E(G)→{0,1,2}\tau:E(G)\to\{0,1,2\} be a proper edge-colouring, and let s:A→{0,1}s:A\to\{0,1\} satisfy s(NG(b))={0,1}s(N_G(b))=\{0,1\} for every b∈Bb\in B. For an edge ee of type ii with endpoint a∈Aa\in A, set

c(e)=(i,s(a)).(5)c(e)=(i,s(a)). \tag*{(5)}

At a∈Aa\in A, put

ha(i)=(i,1−s(a)).(6)h_a(i)=(i,1-s(a)). \tag*{(6)}

At b∈Bb\in B let aia_i be the other endpoint of its type-ii edge and set ti=s(ai)t_i=s(a_i). The vertices aia_i need not be distinct. The triple (t0,t1,t2)(t_0,t_1,t_2) has a unique minority coordinate, namely the position of the bit that occurs once. Let πb\pi_b fix this coordinate and interchange the other two. Put

hb(i)=(πb(i),1−tπb(i)).(7)h_b(i)=(\pi_b(i),1-t_{\pi_b(i)}). \tag*{(7)}

Then these assignments define a strong 6-edge-colouring of T(G)T(G).

Proof. At each a∈Aa\in A, the external and internal palettes are {(i,s(a)):i=0,1,2}\{(i,s(a)):i=0,1,2\} and {(i,1−s(a)):i=0,1,2}\{(i,1-s(a)):i=0,1,2\}. At each b∈Bb\in B, the internal palette is obtained by complementing the bit in each external colour. Hence every local state uses the six colours exactly once. It remains to check compatibility between adjacent triangles. By (2.3), every colour common to their internal palettes must lie opposite the connecting edge at one or both endpoints.

For an edge aiba_i b of type ii, the intersection of its internal palettes is

Iai∩Ib={(j,1−ti):tj=ti}.I_{a_i}\cap I_b=\{(j,1-t_i):t_j=t_i\}.

If ii is the minority coordinate, this intersection is {(i,1−ti)}\{(i,1-t_i)\}, and its colour is opposite the edge at both ends. Otherwise, let jj be the other majority coordinate. The intersection is {(i,1−ti),(j,1−ti)}\{(i,1-t_i),(j,1-t_i)\}. Its first colour is opposite the edge at aia_i, and its second is opposite the edge at bb, since πb(i)=j\pi_b(i)=j. Thus (3) holds on every edge, and Lemma 2.1 completes the proof.

Example 3.6. If the neighbour bits at bb are (t0,t1,t2)=(0,0,1)(t_0,t_1,t_2)=(0,0,1), then

port ii012
cb(i)c_b(i)(0,0)(0,0)(1,0)(1,0)(2,1)(2,1)
hb(i)h_b(i)(1,1)(1,1)(0,1)(0,1)(2,0)(2,0)

Here πb\pi_b interchanges 0, 1 and fixes 2. Thus one first complements the bits of the three external colours and then exchanges the first two resulting colours; the minority position stays fixed.

The matching used to construct ss and the proper edge-colouring τ\tau may be chosen independently. Combining the preceding lemmas gives the first part of the bipartite result.

Corollary 3.7. Let GG be a connected loopless cubic bipartite multigraph that is not det-extremal. Then χs′(T(G))=6\chi_s'(T(G))=6.

Proof. Lemma 3.4 supplies the bits and Lemma 3.5 gives a strong 6-edge-colouring. The reverse inequality is (1).

Rooted replacements in the det-extremal case

For a det-extremal graph, Lemma 3.4 rules out a binary assignment that makes every neighbourhood in BB mixed. Removing one vertex from BB changes the task: we require mixed neighbourhoods only at the remaining vertices of BB, and the three new boundary signatures must reproduce a prescribed local state. The following construction achieves both requirements.

For a loopless cubic multigraph HH and v∈V(H)v\in V(H), write H−vH-v for the 3-pole obtained by deleting vv and retaining its three incident half-edges. Its port signatures refer to the retained endpoints, as in § 2.

Definition 3.8. Let P\mathcal{P} be a cubic 3-pole. We call P\mathcal{P} an exact vertex simulator if, for every ordering of its three ports and every choice of six distinct colours c0,c1,c2,h0,h1,h2c_0,c_1,c_2,h_0,h_1,h_2, its augmented truncation admits a strong edge-colouring with these six colours whose port signatures, in the prescribed order, are

(c0,{h1,h2}),(c1,{h0,h2}),(c2,{h0,h1}).(8)(c_0,\{h_1,h_2\}),\qquad(c_1,\{h_0,h_2\}),\qquad(c_2,\{h_0,h_1\}). \tag*{(8)}

These are the signatures of a canonical triangle with state (c0,c1,c2;h0,h1,h2)(c_0,c_1,c_2;h_0,h_1,h_2). Thus a simulator can be substituted for that triangle without changing any of the data seen by the rest of the coloured graph. Requiring every port order allows any prescribed attachment, rather than only one fixed correspondence.

Theorem 3.9. Let HH be a connected loopless cubic bipartite det-extremal multigraph, and let v∈V(H)v\in V(H). Then the 3-pole H−vH-v is an exact vertex simulator.

Proof. We use a rooted tree to assign the bits. Its predecessor relations will give mixed neighbourhoods away from the deleted vertex, and the absence of even directed cycles will determine the boundary bits. Choose the bipartition so that v∈Bv\in B, and a perfect matching M={aibi:i∈I}M=\{a_i b_i:i\in I\} with v=brv=b_r. By Lemmas 3.3 and 3.2, DMD_M is strongly connected and every directed cycle in DMD_M is odd. Choose an outgoing spanning arborescence T\mathcal{T} rooted at rr: a spanning directed tree with a unique directed path from rr to each vertex. Loops do not enter the tree. Set s(ai)=0s(a_i)=0 if the path from rr to ii in T\mathcal{T} has even length, and s(ai)=1s(a_i)=1 otherwise. For every j≠rj\ne r, its predecessor ii in T\mathcal{T} satisfies s(ai)=0s(a_i)=0, and {ai,aj}\{a_i,a_j\} are both neighbours of bjb_j. Hence s(NH(b))={0,1}s(N_H(b))=\{0,1\} for all b∈B∖{v}b\in B\setminus\{v\}.

For each incoming arc i→ri\to r, the tree path from rr to ii followed by that arc is a directed cycle, including the loop itself when i=ri=r. Its odd length forces ii to have even tree depth. Since s(ar)=0s(a_r)=0, it follows that

s(a)=0for all a∈NH(v).(9)s(a)=0\quad\text{for all }a\in N_H(v). \tag*{(9)}

Thus only the deleted vertex has a monochromatic neighbourhood in BB. After deletion each retained vertex of BB satisfies the mixed-bit condition, and the three incidences at vv retain distinct types even when they have the same neighbour. Choose a proper 3-edge-colouring τ\tau of HH and apply (3.1)--(3.3) to H−vH-v. The proof of Lemma 3.5 verifies every ordinary interface. By (3.5), the signatures of the dangling ports, indexed by their types, are

((i,0),{(j,1):j≠i}),i=0,1,2.((i,0),\{(j,1):j\ne i\}),\qquad i=0,1,2.

Name the three types at vv according to the prescribed port order. Relabelling (i,0)(i,0) as cic_i and (i,1)(i,1) as hih_i gives (8).

Lemma 3.10. Let KK be a loopless cubic multigraph, let φ\varphi be a strong 6-edge-colouring of T(K)T(K), and let x∈V(K)x \in V(K). Let P\mathcal{P} be an exact vertex simulator, and let K′K' be obtained by replacing xx with P\mathcal{P} according to any bijection between the three incidences at xx and the three ports of P\mathcal{P}. Then T(K′)T(K') admits a strong 6-edge-colouring that agrees with φ\varphi outside the replacement.

Proof. Write the local state at xx, in attachment order, as (c0,c1,c2;h0,h1,h2)(c_0,c_1,c_2;h_0,h_1,h_2). Realise (8) in the simulator. The new signatures equal the old ones at xx, so every outside interface remains valid. The internal interfaces of the pole are valid by definition. Lemma 2.1 gives the required colouring.

The rooted construction also gives a family of 2-poles whose ends can be joined cyclically. For an edge ee of a cubic multigraph HH, write H−eH-e for the 2-pole retaining a dangling half-edge at each endpoint of the deleted edge. When HH is connected, bipartite and det-extremal, this pole realises every boundary prescription of the double-edge block.

Corollary 3.11. Let k≥2k \ge2. For each i∈{1,…,k}i \in\{1,\ldots,k\}, let HiH_i be a connected loopless cubic bipartite det-extremal multigraph and let ei∈E(Hi)e_i \in E(H_i). If GG is obtained by joining disjoint copies of the 2-poles Hi−eiH_i-e_i cyclically, then χs′(T(G))=6\chi'_s(T(G))=6.

Proof. For any connected loopless cubic bipartite det-extremal multigraph HH and any edge ee incident with zz, the 2-pole H−eH-e realises every boundary prescription in (4). Indeed, start with a colouring of a double-edge block with the prescribed signatures and replace one of its vertices by the exact vertex simulator H−zH-z from Theorem 3.9. Assign the port corresponding to ee to the outside port of the replaced vertex. The unreplaced vertex of the block takes the role of zz: its two non-boundary edges restore the other two incidences of zz. The resulting pole is therefore H−eH-e, with a dangling half-edge at each endpoint of ee. The replacement preserves the prescribed boundary signatures by the interface criterion.

Apply this observation to every Hi−eiH_i-e_i, using the boundary prescriptions for a cycle of kk double-edge blocks in the proof of Proposition 2.4. All joins are compatible, so the interface criterion supplies the colouring. The lower bound follows from (1).

The simple case

It remains to consider det-extremal bases. We first settle the case in which GG is simple. For a 3-connected base the rooted replacement works along a decomposition into Heawood graphs. For a base of connectivity two, a suitable 2-edge cut lets us join a colouring built in this way to one given by the binary formula.

A vertex-sum of disjoint simple cubic graphs X,YX,Y at vertices x,yx,y is obtained by deleting x,yx,y and joining their neighbour sets by a bijection. If X,YX,Y are bipartite, choose their bipartitions so that the new edges join opposite parts. We use the following characterisation of McCuaig [15]; see also [7] and [4 Theorem 1.1].

Theorem 3.12. Let GG be a simple 3-connected cubic bipartite graph. Then GG is det-extremal if and only if it can be obtained from copies of the Heawood graph by repeated vertex-sums.

McCuaig’s characterisation explains why we start from the Heawood graph. Once its truncation is coloured, Theorem 3.9 supplies the rooted pieces for subsequent vertex-sums, without requiring colourings of their entire truncations. We first give the initial Heawood colouring.

Let H\mathbb{H} be the Heawood graph with vertices Ai,BiA_i,B_i, indexed by Z\mathbb{Z}, and edges

AiBi,AiBi+1,AiBi+3.A_iB_i,\qquad A_iB_{i+1},\qquad A_iB_{i+3}.

Give these edges types 0, 1, 2, respectively. At AiA_i the port order is (Bi,Bi+1,Bi+3)(B_i,B_{i+1},B_{i+3}); at BiB_i it is (Ai,Ai−1,Ai−3)(A_i,A_{i-1},A_{i-3}). This specifies a proper edge-colouring by types.

Lemma 3.13. Let H\mathbb{H} be the Heawood graph. Then T(H)T(\mathbb{H}) admits a strong 6-edge-colouring.

Proof. Assign the states in Table 1, using colours 0,1,…,50,1,\ldots,5 and the port orders above. The corresponding colouring is shown in Figure 2.

iiState at AiA_iState at BiB_i
0(0,2,4;1,3,5)(0,2,4;1,3,5)(0,3,5;1,2,4)(0,3,5;1,2,4)
1(1,2,4;0,3,5)(1,2,4;0,3,5)(1,2,5;3,0,4)(1,2,5;3,0,4)
2(0,3,4;5,2,1)(0,3,4;5,2,1)(0,2,4;1,5,3)(0,2,4;1,5,3)
3(1,3,5;2,0,4)(1,3,5;2,0,4)(1,3,4;0,5,2)(1,3,4;0,5,2)
4(1,2,5;0,3,4)(1,2,5;0,3,4)(1,3,4;5,2,0)(1,3,4;5,2,0)
5(0,2,5;1,4,3)(0,2,5;1,4,3)(0,2,4;3,1,5)(0,2,4;3,1,5)
6(1,3,4;0,2,5)(1,3,4;0,2,5)(1,2,5;4,3,0)(1,2,5;4,3,0)

Table 1. A complete 6-colour state assignment for the Heawood graph.

A strong 6-edge-colouring of the Heawood graph in the classical circular layout

Figure 2. A strong 6-edge-colouring of T(H)T(H) in the classical circular layout of the Heawood graph. Clockwise from the top, the canonical triangles follow the Hamiltonian cycle A0,B1,A1,B2,…,A6,B0A_0,B_1,A_1,B_2,\ldots,A_6,B_0; the seven chords correspond to the edges AiBi+3A_iB_{i+3}. Red numerals are the edge colours 0,…,50,\ldots,5 from Table 1.

Every state contains the six distinct colours, and the external entries agree at the ends of every edge. To verify (3), put d0=0,d1=1,d2=3d_0=0,d_1=1,d_2=3 and define

Ji,k=IAi∩IBi+dk,Ki,k={hAi(k),hBi+dk(k)}.J_{i,k}=I_{A_i}\cap I_{B_{i+d_k}},\qquad K_{i,k}=\{h_{A_i}(k),h_{B_{i+d_k}}(k)\}.

Table 2 lists Ji,k;Ki,kJ_{i,k};K_{i,k} for all 21 edges. Each first set is contained in the second, as required. The result follows from Lemma 2.1.

iitype 0type 1type 2
0{1};{1}\{1\};\{1\}{3};{0,3}\{3\};\{0,3\}{5};{2,5}\{5\};\{2,5\}
1{0,3};{0,3}\{0,3\};\{0,3\}{3,5};{3,5}\{3,5\};\{3,5\}{0,5};{0,5}\{0,5\};\{0,5\}
2{1,5};{1,5}\{1,5\};\{1,5\}{2,5};{2,5}\{2,5\};\{2,5\}{1,5};{1,5}\{1,5\};\{1,5\}
3{0,2};{0,2}\{0,2\};\{0,2\}{0,2};{0,2}\{0,2\};\{0,2\}{0,4};{0,4}\{0,4\};\{0,4\}
4{0};{0,5}\{0\};\{0,5\}{3};{1,3}\{3\};\{1,3\}{4};{4}\{4\};\{4\}
5{1,3};{1,3}\{1,3\};\{1,3\}{3,4};{3,4}\{3,4\};\{3,4\}{3,4};{3,4}\{3,4\};\{3,4\}
6{0};{0,4}\{0\};\{0,4\}{2};{2}\{2\};\{2\}{5};{3,5}\{5\};\{3,5\}

Table 2. Verification of every interface in the Heawood seed.

To follow the vertex-sum expression supplied by Theorem 3.12 recursively, we need the intermediate graphs to be det-extremal so that Theorem 3.9 applies. McCuaig’s characterisation gives this once their 3-connectivity is established, as in the next lemma.

Lemma 3.14. Let XX and YY be disjoint simple 3-connected cubic bipartite graphs, and let x∈V(X)x \in V(X) and y∈V(Y)y \in V(Y). Every vertex-sum of XX and YY at xx and yy is a simple 3-connected cubic bipartite graph.

Proof. Simplicity, cubicity and bipartiteness are immediate. Let SS contain at most two vertices of the vertex-sum. If SS meets each side in at most one vertex, both sides remain connected by the 3-connectivity of X,YX,Y, and at least one joining edge survives. Otherwise, by symmetry, S⊆V(X)∖{x}S \subseteq V(X) \setminus\{x\}. The side Y−yY-y remains connected. Every component of X−(S∪{x})X-(S \cup\{x\}) contains a surviving neighbour of xx, since otherwise it would be separated from xx in X−SX-S. Each such component therefore has a joining edge to Y−yY-y. Thus deletion of SS leaves a connected graph.

We can now combine the Heawood seed with the replacement construction. At each vertex-sum, a colouring on one side supplies the boundary state to be realised by the simulator on the other side.

Lemma 3.15. Let GG be a simple 3-connected cubic bipartite det-extremal graph. Then T(G)T(G) admits a strong 6-edge-colouring, which can be constructed from a vertex-sum expression for GG in terms of Heawood graphs.

Proof. By Theorem 3.12, GG has an expression as repeated vertex-sums of Heawood graphs. Every intermediate graph is simple and 3-connected by Lemma 3.14, and det-extremal by Theorem 3.12. We induct on this expression. Lemma 3.13 colours each initial copy. If an intermediate graph is a vertex-sum of X,YX,Y at x,yx,y, colour T(X)T(X) by induction and replace xx by Y−yY-y. We need only the colouring on the XX side: the pole Y−yY-y is assigned the signatures of the removed triangle at xx. Theorem 3.9 and Lemma 3.10 extend the colouring across this replacement.

This settles the 3-connected case. We turn to simple det-extremal bases of vertex connectivity two. We shall find a 2-edge cut for which one closure is simple, 3-connected and det-extremal, while the other is simple and non-det-extremal. The Heawood construction and the binary colouring formula will then colour the truncations of the two closures separately.

For a 2-edge cut δ(S)\delta(S), its shores are SS and V(G)∖SV(G) \setminus S. When the two boundary endpoints on a shore are distinct, adding an edge between them to the subgraph induced by that shore gives its closure; the added edge is its marker. These markers are the two edges to which we apply Lemma 2.2: deleting them and restoring the original cut edges joins the two colourings to give a colouring of T(G)T(G). The next lemma shows that both closures are connected cubic bipartite multigraphs. A closure may initially have parallel edges; simplicity will be established when the appropriate cut is chosen.

Lemma 3.16. Let GG be a connected loopless cubic bipartite multigraph with partition sets AA and BB. Then the following statements hold.

  1. GG is bridgeless and has no cut vertex.

  2. For every 2-edge cut, each shore induces a connected subgraph and contains equally many vertices of AA and BB. Its two boundary endpoints are distinct and belong to opposite partition sets, so its closure is a connected loopless cubic bipartite multigraph.

  3. If GG is simple, then GG has vertex connectivity two if and only if it has a 2-edge cut. In either closure of such a cut, every pair of parallel edges contains the marker.

Proof. Write dA(S)d_A(S) and dB(S)d_B(S) for the numbers of edges leaving SS at vertices of AA and BB, respectively. Counting degrees gives

3(∣A∩S∣−∣B∩S∣)=dA(S)−dB(S).(10)3\left(\lvert A \cap S\rvert-\lvert B \cap S\rvert\right)=d_A(S)-d_B(S). \tag*{(10)}

A bridge would make the right-hand side ±1\pm1. A cut vertex would have at least two edges to each of at least two components, since no incident edge is a bridge. This proves (i).

If ∣δ(S)∣=2\lvert\delta(S)\rvert=2, the identity forces dA(S)=dB(S)=1d_A(S)=d_B(S)=1 and ∣A∩S∣=∣B∩S∣\lvert A \cap S\rvert=\lvert B \cap S\rvert. Each component of a shore would need at least two boundary edges, so the shore is connected. Adding the marker between the two boundary vertices gives the closure in (ii). For (iii), suppose that GG is simple and deleting x,yx,y disconnects GG. Each resulting component has at least two boundary edges. If none has exactly two, there are exactly two components C,DC,D, each with three boundary edges, and xyxy is not an edge. Neither xx nor yy is a cut vertex, so both have neighbours in both components. Renaming x,yx,y if necessary, CC has two edges to yy and one to xx, and then C∪{y}C \cup\{y\} gives a 2-edge cut. Conversely, a shore of a 2-edge cut contains vertices other than its two boundary vertices: a two-vertex shore of a simple cubic graph would have at least four boundary edges. Removing its two boundary vertices therefore disconnects GG. Finally, simplicity of GG means that only a marker can introduce parallel edges into a closure.

An arbitrary 2-edge cut need not give a 3-connected closure. We first recall the structural result that permits a suitable choice. For a simple 2-connected cubic bipartite graph GG, declare two vertices equivalent if they coincide or are joined by three edge-disjoint paths. Contracting the equivalence classes and deleting loops gives a cactus CC: a connected multigraph whose blocks are cycles, including cycles of length two.

At a vertex xx of CC, start with the subgraph induced by its class. For each pair of edges incident with xx that forms a 2-edge cut of CC, add a marker between their endpoints in that class. The resulting piece GxG_x is either a 3-bond (two vertices joined by three parallel edges) or a simple 3-connected cubic bipartite graph. These are the decomposition and pieces of [7 Section 2]; see also [4, Definition 5.1 and Observation 5.2]. We need only the case in which xx has degree two in the cactus.

Theorem 3.17. Let GG be a simple cubic bipartite det-extremal graph of connectivity two, with decomposition cactus CC and pieces GxG_x as above. If deg⁡C(x)=2\deg_C(x)=2, then GxG_x is det-extremal.

This follows from the structural theorem of Funk, Jackson, Labbate and Sheehan [7 Theorem 2.3]; see also [4, Theorem 5.4]. The next lemma gives both closures needed for the colouring argument.

Lemma 3.18. Let GG be a connected simple cubic bipartite det-extremal graph with vertex connectivity two. Then GG has a 2-edge cut with simple closures P,RP,R such that PP is 3-connected and det-extremal, whereas RR is not det-extremal.

Proof. The decomposition cactus CC has at least two vertices, since GG has connectivity two. Choose an end cycle of CC, that is, a cycle containing at most one cut vertex, and let zz be a non-cut vertex on it. Then deg⁡C(z)=2\deg_C(z)=2. Its class SS therefore has exactly two boundary edges, and the piece P=GzP=G_z is the closure of G[S]G[S] with exactly one marker. Theorem 3.17 makes PP det-extremal. If PP were a 3-bond, its two nonmarker edges would be parallel edges of GG, contradicting simplicity. The description of the pieces therefore makes PP simple and 3-connected.

Let RR be the other closure. By Lemma 3.16, both closures are connected cubic bipartite multigraphs. Write their markers as e=uve=uv in PP and f=xyf=xy in RR, so that GG is obtained by deleting e,fe,f and adding uy,xvuy,xv. Choose perfect matchings p0,p1p_0,p_1 of PP avoiding and containing ee, respectively, and r0,r1r_0,r_1 of RR avoiding and containing ff. Such matchings exist because each closure admits a proper 3-edge-colouring. Let CPC_P and CRC_R be the cycles containing the markers in p0△p1p_0 \mathbin{\triangle} p_1 and r0△r1r_0 \mathbin{\triangle} r_1, respectively. Cycles of length two are allowed in RR. Since PP is det-extremal, Lemma 3.3 gives ∣CP∣≡2(mod4)|C_P| \equiv2 \pmod{4}.

Joining the paths CP−eC_P-e and CR−fC_R-f with uy,xvuy,xv gives a cycle in GG of length ∣CP∣+∣CR∣|C_P|+|C_R|. It is alternating with respect to the perfect matching

M=((p1∪r1)∖{e,f})∪{uy,xv}.M=((p_1 \cup r_1)\setminus\{e,f\})\cup\{uy,xv\}.

Indeed, the two joining edges belong to MM, and each path alternates with its first and last edges outside MM. Since GG is det-extremal, another application of Lemma 3.2 yields

∣CP∣+∣CR∣≡2(mod4),hence∣CR∣≡0(mod4).|C_P|+|C_R| \equiv2 \pmod{4}, \qquad\text{hence}\qquad|C_R| \equiv0 \pmod{4}.

This holds for every choice of r0,r1r_0,r_1 as above. If ff were parallel to an old edge gg, choose r1r_1 containing ff and put r0=(r1∖{f})∪{g}r_0=(r_1\setminus\{f\})\cup\{g\}. Then CRC_R would have length two, a contradiction. By Lemma 3.16, every possible pair of parallel edges in RR contains its marker, so RR is simple. Finally, CRC_R is an r1r_1-alternating cycle of length divisible by four. Lemma 3.2 therefore shows that RR is not det-extremal.

Theorem 3.19. Let GG be a connected simple cubic bipartite graph. Then χs′(T(G))=6\chi'_s(T(G))=6.

Proof. Corollary 3.7 settles the non-det-extremal case. If GG is det-extremal, Lemma 3.16 and cubicity leave vertex connectivities two and three. In the 3-connected case, Lemma 3.15 gives the required colouring. If the connectivity is two, use the closures P,RP,R of Lemma 3.18. Lemma 3.15 colours T(P)T(P) and Corollary 3.7 colours T(R).T(R). Lemma 2.2 joins these colourings along the markers, and (1) gives equality.

:::

The marked core of a minimum counterexample

Theorem 3.19 rules out a simple counterexample, and Corollary 3.7 rules out a non-det-extremal one. Thus a counterexample to Theorem 1.1 of minimum order would be det-extremal and have parallel edges. We show that suppressing its parallel-edge blocks gives a simple cubic core. The edges on which these blocks must be restored carry a marking constrained by the signs of the perfect matchings.

For a cubic multigraph PP and F⊆E(P)F \subseteq E(P), let PFP_F be obtained by inserting one block BB on each edge of FF. Call the edges of FF marked. A signing σ:E(P)→{±1}\sigma:E(P)\to\{\pm1\} of a simple bipartite graph PP with a perfect matching is Pfaffian if sgn⁡(M)∏e∈Mσ(e)\operatorname{sgn}(M)\prod_{e\in M}\sigma(e) is the same for all perfect matchings MM of PP. Orient positive edges from one partition set to the other and negative edges in the reverse direction. The resulting orientation is Pfaffian exactly when the signing is Pfaffian; see the survey of Thomas [18 Theorem 3.4]. A cycle CC is central if P−V(C)P-V(C) has a perfect matching.

Two elementary configurations explain the restrictions on a minimum counterexample: three marks at a single vertex, and three blocks on the three edges of the 3-bond. For these two constructions take Ω={1,2,3,4,5,6}\Omega=\{1,2,3,4,5,6\}.

Lemma 3.20. Let KK be a loopless cubic multigraph whose truncation has a strong 6-edge-colouring. Inserting one BB on each of the three edges incident with a vertex xx preserves colourability while fixing every retained state except the state at xx, and every external colour away from those three edges.

Proof. Change the state at xx from (c0,c1,c2;h0,h1,h2)(c_0,c_1,c_2;h_0,h_1,h_2) to (h0,h1,h2;c0,c1,c2)(h_0,h_1,h_2;c_0,c_1,c_2). On the block at port ii, prescribe boundary colours cic_i toward the old neighbour and hih_i toward xx, with common pair Wi={hj:j≠i}W_i=\{h_j:j\ne i\}. Proposition 2.3 applies. The outer signature is the former signature at xx, while WiW_i is disjoint from the new pair {cj:j≠i}\{c_j:j\ne i\} at the inner interface. All other interfaces are unchanged. If KK is bipartite, the new base is also bipartite.

Proposition 3.21. The base consisting of two vertices joined through three disjoint copies of BB is bipartite and has a truncation of strong chromatic index six.

Proof. At the two new vertices use (1,2,3;4,5,6)(1,2,3;4,5,6) and (2,3,1;4,5,6)(2,3,1;4,5,6), ordering ports by the three blocks. Prescribe the following data on those blocks, listing their two boundary colours and common exposed pair:

(1,2,{3,4}),(2,3,{1,5}),(3,1,{2,6}).(1,2,\{3,4\}),\qquad(2,3,\{1,5\}),\qquad(3,1,\{2,6\}).

Proposition 2.3 realises them. At either new vertex the exposed pairs are {5,6},{4,6},{4,5}\{5,6\},\{4,6\},\{4,5\}, respectively, disjoint from the corresponding block pairs. All joins are compatible. Each branch has underlying length three, proving bipartiteness. The local lower bound gives equality.

Lemma 3.22. A counterexample GG of minimum order to Theorem 1.1 has the form PFP_F, where PP is simple, 3-connected, cubic and bipartite, F≠∅F\ne\varnothing, and every vertex is incident with at most two edges of FF. Moreover, GG is det-extremal and the signing of PP negative precisely on FF is Pfaffian.

Proof. Theorem 3.19 and Corollary 3.7 imply that GG is non-simple and det-extremal. By Lemma 3.16, each shore of a 2-edge cut is connected and balanced, and its two boundary vertices are in opposite partition sets. Both closures are therefore connected loopless cubic bipartite multigraphs of smaller order. If neither is M0M_0, minimality gives a colouring of each truncation. Gluing along the markers as in Lemma 2.2 would then colour T(G)T(G), a contradiction. Hence every 2-edge cut isolates a single block BB.

Triple edges would give G=M0G=M_0; double-edge blocks are vertex-disjoint. If they cover GG, Proposition 2.4 colours their cycle. Otherwise no two blocks are adjacent: their four-vertex shore would have a 2-edge boundary, forcing the complement to be one block and again giving a cycle. Suppressing all blocks therefore gives a connected loopless cubic bipartite multigraph PP with G=PFG=P_F.

If PP has exactly two parallel edges uvuv, at least one is marked. The vertices u,vu,v and the blocks on these edges form a shore of order at least four with a 2-edge boundary. Its complement must be a single block, whose suppression would give a third edge, a contradiction. Thus PP is simple unless P=M0P=M_0. In the latter case zero marked edges give the excluded M0M_0; one gives a cycle of two blocks; two give a non-det-extremal graph, since a direct and an expanded connection form a central 4-cycle; and three give the theta coloured in Proposition 3.21. All cases are excluded.

If PP had a 2-edge cut, both shores would have at least four vertices, since PP is simple, cubic and bipartite. The cut would lift to one of GG: for each marked cut edge, cut one outside edge of its block. Neither shore of the lifted cut would be a single BB. Thus PP is 3-edge-connected and, being simple and cubic, 3-vertex-connected. If all three edges at a vertex were marked, suppressing their blocks would give a smaller admissible graph, whose truncation is colourable by minimality: it still contains the vertices of the simple core PP, so it is not M0M_0. Lemma 3.20 would extend this colouring. The marked degree is therefore at most two. A perfect matching of PFP_F uses either both or neither of the outside edges of each block. It therefore projects to a perfect matching MM of PP: for a marked edge in MM it uses both outside edges, and for a marked edge outside MM it chooses one of the two internal edges. Every MM has such a lift M~\widetilde{M}. Order the new vertices after the old ones, in the same block order on both sides. Relative to matching each new pair internally, passing through a block on e∈M∩Fe \in M \cap F interchanges two matched images. Thus

sgn⁡(M~)=(−1)∣M∩F∣sgn⁡(M).\operatorname{sgn}(\widetilde{M})=(-1)^{|M\cap F|}\operatorname{sgn}(M).

Since GG is det-extremal, the signing negative precisely on FF is Pfaffian.

The signing now explains which local configurations have to be restored. First suppose that the core contains a 4-cycle.

Lemma 3.23. Let PP be a simple cubic bipartite graph with a Pfaffian signing negative precisely on FF. Each 4-cycle of PP contains either one or three edges of FF.

Proof. Every 4-cycle CC in PP is central. Indeed, deleting it preserves the equality of the partition sizes. If Hall’s condition failed for a set XX on one side of P−V(C)P-V(C), degree counting would give 3∣X∣≤3∣NP−V(C)(X)∣+23|X| \le3|N_{P-V(C)}(X)|+2: the two opposite-part vertices of CC have only two incidences outside CC. This contradicts ∣NP−V(C)(X)∣<∣X∣|N_{P-V(C)}(X)| < |X|. Extend a perfect matching of P−V(C)P-V(C) by either of the two matchings of CC. Switching between them multiplies the permutation sign by −1-1 and the product of edge signs by (−1)∣F∩E(C)∣(-1)^{|F\cap E(C)|}. Their product must be unchanged, so the number of marks on CC is odd.

When PP has no 4-cycle, the corresponding replacement will be a Heawood graph with one vertex deleted. To locate it we must keep the signs of the marked edges when taking a closure.

For a 3-edge cut, the closure of a shore is obtained by replacing the opposite shore with a new vertex, called the root, while preserving the three cut incidences. The cut is nontrivial if neither shore is a single vertex. A graph is cyclically 4-edge-connected if no edge cut of size at most three has a cycle on both shores.

Lemma 3.24. Let PP be a simple 3-connected cubic bipartite graph with a Pfaffian signing. Each closure of a nontrivial 3-edge cut is simple, 3-connected, cubic and bipartite, and admits a Pfaffian signing agreeing with the original signing on all non-root edges.

Proof. The cut count (3.6) puts all three boundary incidences of a shore in the same partition set. A nontrivial shore has at least five vertices; its boundary vertices are distinct, since otherwise at most two vertices would separate it from the other shore. Adding a root at these vertices gives a simple cubic bipartite closure. Any edge cut of size at most two can be taken on a shore avoiding the root and would lift to such a cut of PP. The closure is therefore 3-edge-connected and 3-vertex-connected.

Every perfect matching crosses the original cut once: on each shore the partition sizes differ by one and the boundary incidences all belong to the larger set. Let H,RH,R be the closures, with root edges numbered 1,2,31,2,3 according to the original cut edges. For each ii, a perfect matching of RR using root edge ii; one exists since RR is cubic and bipartite. Every perfect matching of HH using root edge ii combines with it to give a perfect matching of PP. The symmetric difference of two such matchings lies in H−rH-r, so extension preserves the ratio of their signed determinant terms. The Pfaffian signing of PP therefore makes all terms in this class have a common sign αi\alpha_i in HH, initially assigning positive signs to its root edges. Assigning sign αi\alpha_i to root edge ii makes every term positive, without changing any non-root sign. Apply the same argument to RR.

Lemma 3.25. Let PP be a simple 3-connected cubic bipartite Pfaffian graph without a 4-cycle. Then PP is Heawood or has a nontrivial 3-edge cut with one Heawood closure.

Proof. By [7 Lemma 4.6], a cyclically 4-edge-connected cubic bipartite Pfaffian graph other than Heawood contains two vertex-disjoint 4-cycles. This proves the assertion when PP is cyclically 4-edge-connected. Otherwise choose a smallest shore SS of a nontrivial 3-edge cut and let HH be its closure, with root rr. By Lemma 3.24, HH is simple, 3-connected, cubic, bipartite and Pfaffian. It is cyclically 4-edge-connected: a nontrivial 3-edge cut in HH would have a shore avoiding rr, strictly contained in SS, and lifting to a smaller such shore in PP. If HH were not Heawood, its two disjoint 4-cycles would include one avoiding rr, hence a 4-cycle of PP, a contradiction.

Restoring the marked pieces and completing the proof

The core either contains a 4-cycle or has the Heawood structure described in Lemma 3.25. For each possibility we give a local replacement that extends a colouring of a smaller graph across the deleted piece.

The marked 4-cycle

By Lemma 3.23, a 4-cycle in the marked core expands to one of just two 4-poles. Removing it and pairing its four outside incidences gives two ordinary edges. In a colouring of the smaller graph each edge has one external colour and disjoint exposed pairs at its ends. The following lemma shows that these are the only assumptions needed to put the 4-pole back. In both local constructions below we name the colours 0,1,2,3,4,5.

Lemma 3.26. Let R1R_1 be obtained from the cycle v0v1v2v3v0v_0v_1v_2v_3v_0 by inserting BB on v0v1v_0v_1, and let R3R_3 instead have BB on v0v1,v1v2,v2v3v_0v_1,v_1v_2,v_2v_3. Give each viv_i one outside port. If the signatures prescribed by the exterior, in the order v0,v1,v2,v3v_0,v_1,v_2,v_3, are

(c,U),(c,V),(d,X),(d,Y),(c,U),\qquad(c,V),\qquad(d,X),\qquad(d,Y),

where U,VU,V are disjoint two-element subsets of Ω∖{c}\Omega\setminus\{c\} and X,YX,Y are disjoint two-element subsets of Ω∖{d}\Omega\setminus\{d\}, then the augmented truncation of each 4-pole has a strong 6-edge-colouring compatible with these signatures.

Proof. Order the ports at each viv_i as outside, forward, backward. In a state (a,b,c;d,e,f)(a,b,c;d,e,f) the outside port has signature (a,{e,f})(a,\{e,f\}). By Proposition 2.3, a block can join signatures (a,P),(b,Q)(a,P),(b,Q) whenever a≠ba \ne b and a two-element subset W⊆Ω∖(P∪Q∪{a,b})W \subseteq\Omega\setminus(P \cup Q \cup\{a,b\}) exists; use WW as its common exposed pair.

For c≠dc \ne d, Table 3 realises the following exposed-pair patterns in both 4-poles, with outside colours c,c,d,dc,c,d,d and normalisation (c,d,a,b,p,q)=(0,1,2,3,4,5)(c,d,a,b,p,q)=(0,1,2,3,4,5):

P0P_0P1P_1P2P_2P3P_3
AA{a,b}\{a,b\}{p,q}\{p,q\}{p,q}\{p,q\}{a,b}\{a,b\}
BB{a,b}\{a,b\}{d,p}\{d,p\}{a,q}\{a,q\}{b,p}\{b,p\}
B∗B^*{d,p}\{d,p\}{a,b}\{a,b\}{b,p}\{b,p\}{a,q}\{a,q\}
CC{d,a}\{d,a\}{d,b}\{d,b\}{a,p}\{a,p\}{b,q}\{b,q\}

Table 3.

We choose a pattern whose four pairs avoid U,V,X,YU,V,X,Y, respectively. Put Z=Ω∖{c,d}Z=\Omega\setminus\{c,d\}.

If d∈Ud \in U, write U={d,u}U=\{d,u\} and Z=V∪{u˙,t}Z=V \cup\{\dot{u},t\}. Set D=XD=X if c∉Xc \notin X, and D=Z∖YD=Z \setminus Y otherwise. Then ∣D∣=2|D|=2, X∩Z⊆DX \cap Z \subseteq D and D∩Y=∅D \cap Y=\varnothing. If D=VD=V, use AA with {a,b}=V\{a,b\}=V and {p,q}={u,t}\{p,q\}=\{u,t\}. Otherwise write D={b,p}D=\{b,p\} with b≠ub \ne u and p∉Vp \notin V: for D={u,t}D=\{u,t\} take (b,p)=(t,u)(b,p)=(t,u); otherwise take b∈D∩Vb \in D \cap V and p∈D∖Vp \in D \setminus V. Write Z∖D={a,q}Z \setminus D=\{a,q\} with a≠ua \ne u. Pattern BB works: {a,b}\{a,b\} avoids UU, {d,p}\{d,p\} avoids VV, {a,q}=Z∖D\{a,q\}=Z \setminus D avoids XX, and {b,p}=D\{b,p\}=D avoids YY. If d∈Vd \in V, interchange U,VU,V and simultaneously X,YX,Y in this argument, obtaining AA or B∗B^* in the original order. The latter has its own realisation; no reflection of the 4-pole is assumed.

If d∉U∪Vd \notin U \cup V, then U,VU,V partition ZZ. Set D=YD=Y if c∉Yc \notin Y, and D=Z∖XD=Z \setminus X otherwise. Now D∩X=∅D \cap X=\varnothing and Y∩Z⊆DY \cap Z \subseteq D. For D=UD=U, use AA with {a,b}=V,{p,q}=U\{a,b\}=V,\{p,q\}=U. Otherwise choose a∈D∩Va \in D \cap V and b∈(Z∖D)∩Ub \in(Z \setminus D) \cap U, which exist since D≠UD \ne U, and write D={a,p}D=\{a,p\} and Z∖D={b,q}Z \setminus D=\{b,q\}. Pattern CC works: {d,a},{d,b}\{d,a\},\{d,b\} avoid U,VU,V, and {a,p}=D,{b,q}=Z∖D\{a,p\}=D,\{b,q\}=Z \setminus D avoid X,YX,Y.

For c=dc=d, both 4-poles realise

D:(P0,P1,P2,P3)=({a,b},{p,q},{b,p},{a,q}),D:\qquad(P_0,P_1,P_2,P_3)=(\{a,b\},\{p,q\},\{b,p\},\{a,q\}),

with outside colour cc and normalisation (c,a,b,p,q,r)=(0,1,2,3,4,5)(c,a,b,p,q,r)=(0,1,2,3,4,5). Put Z=Ω∖{c}Z=\Omega\setminus\{c\} and let {r0}=Z∖(U∪V)\{r_0\}=Z \setminus(U \cup V), {s0}=Z∖(X∪Y)\{s_0\}=Z \setminus(X \cup Y). The family DD is invariant under simultaneously swapping its first two and last two entries, by renaming (a,b,p,q)(a,b,p,q) as (p,q,a,b)(p,q,a,b), and under swapping its last two entries, by renaming them as (b,a,q,p)(b,a,q,p). These are symmetries of colour assignments, not of the pole. If r0≠s0r_0 \ne s_0, they allow us to assume U={s0,u}U=\{s_0,u\} with u∈Xu \in X. Write X={u,a}X=\{u,a\}, take any b∈Yb \in Y and put (p,q)=(s0,u)(p,q)=(s_0,u). The colours a,b,p,qa,b,p,q are distinct, and {a,b},{p,q}=U\{a,b\},\{p,q\}=U, {b,p},{a,q}=X\{b,p\},\{a,q\}=X avoid U,V,X,YU,V,X,Y, respectively.

If r0=s0r_0=s_0 and X∉{U,V}X \notin\{U,V\}, write U={u1,u2}U=\{u_1,u_2\}, V={v1,v2}V=\{v_1,v_2\}, X={u1,v1}X=\{u_1,v_1\}, Y={u2,v2}Y=\{u_2,v_2\}. Taking (a,b,p,q)=(v1,v2,u2,u1)(a,b,p,q)=(v_1,v_2,u_2,u_1) gives pairs V,U,Y,XV,U,Y,X. In the two remaining cases normalise c=0c=0, U={1,2}U=\{1,2\}, Y={3,4}Y=\{3,4\}, r0=5r_0=5 and use

The required disjointness is immediate.

Every state in the table is a permutation of the palette. Direct interfaces have equal external colours and disjoint exposed pairs; at each block the external colours differ and the listed WijW_{ij} avoids both colours and both endpoint pairs. Proposition 2.3 and the interface criterion therefore verify all seven patterns. The preceding choices cover every outside prescription.

PatternPolev0v_0v1v_1v2v_2v3v_3W01W_{01}W12W_{12}W23W_{23}
AAR1R_1(0,4,5;1,2,3)(0,4,5;1,2,3)(0,2,3;1,4,5)(0,2,3;1,4,5)(1,0,2;3,4,5)(1,0,2;3,4,5)(1,5,0;4,2,3)(1,5,0;4,2,3){0,2}\{0,2\}——
AAR3R_3(0,1,4;5,2,3)(0,1,4;5,2,3)(0,1,2;3,5,4)(0,1,2;3,5,4)(1,0,2;3,4,5)(1,0,2;3,4,5)(1,4,5;0,2,3)(1,4,5;0,2,3){0,4}\{0,4\}{0,5}\{0,5\}{1,4}\{1,4\}
BBR1R_1(0,4,5;1,3,2)(0,4,5;1,3,2)(0,3,2;5,4,1)(0,3,2;5,4,1)(1,0,3;4,2,5)(1,0,3;4,2,5)(1,5,0;2,3,4)(1,5,0;2,3,4){0,3}\{0,3\}——
BBR3R_3(0,1,5;4,2,3)(0,1,5;4,2,3)(0,2,3;5,1,4)(0,2,3;5,1,4)(1,0,3;4,2,5)(1,0,3;4,2,5)(1,5,2;0,4,3)(1,5,2;0,4,3){0,2}\{0,2\}{0,1}\{0,1\}{1,3}\{1,3\}
B∗B^*R1R_1(0,2,3;5,1,4)(0,2,3;5,1,4)(0,5,4;1,2,3)(0,5,4;1,2,3)(1,0,5;2,4,3)(1,0,5;2,4,3)(1,3,0;4,5,2)(1,3,0;4,5,2){0,3}\{0,3\}——
B∗B^*R3R_3(0,2,3;5,1,4)(0,2,3;5,1,4)(0,1,4;5,2,3)(0,1,4;5,2,3)(1,2,0;5,3,4)(1,2,0;5,3,4)(1,3,0;4,5,2)(1,3,0;4,5,2){0,1}\{0,1\}{2,4}\{2,4\}{1,3}\{1,3\}
CCR1R_1(0,3,4;5,1,2)(0,3,4;5,1,2)(0,5,2;4,3,1)(0,5,2;4,3,1)(1,0,5;3,2,4)(1,0,5;3,2,4)(1,4,0;2,5,3)(1,4,0;2,5,3){0,1}\{0,1\}——
CCR3R_3(0,3,4;5,1,2)(0,3,4;5,1,2)(0,4,2;5,1,3)(0,4,2;5,1,3)(1,3,0;5,4,2)(1,3,0;5,4,2)(1,4,0;2,5,3)(1,4,0;2,5,3){0,4}\{0,4\}{1,2}\{1,2\}{1,4}\{1,4\}
DDR1R_1(0,4,3;5,1,2)(0,4,3;5,1,2)(0,1,2;5,4,3)(0,1,2;5,4,3)(0,5,1;4,2,3)(0,5,1;4,2,3)(0,3,5;2,1,4)(0,3,5;2,1,4){0,1}\{0,1\}——
DDR3R_3(0,3,5;4,2,1)(0,3,5;4,2,1)(0,2,1;5,3,4)(0,2,1;5,3,4)(0,1,5;4,2,3)(0,1,5;4,2,3)(0,5,2;3,4,1)(0,5,2;3,4,1){0,2}\{0,2\}{0,1}\{0,1\}{0,5}\{0,5\}
E+E^+R1R_1(0,1,5;2,3,4)(0,1,5;2,3,4)(0,2,4;3,1,5)(0,2,4;3,1,5)(0,3,2;1,4,5)(0,3,2;1,4,5)(0,5,3;4,2,1)(0,5,3;4,2,1){0,5}\{0,5\}——
E+E^+R3R_3(0,1,5;2,3,4)(0,1,5;2,3,4)(0,3,2;4,1,5)(0,3,2;4,1,5)(0,1,2;3,5,4)(0,1,2;3,5,4)(0,5,3;4,2,1)(0,5,3;4,2,1){0,3}\{0,3\}{0,1}\{0,1\}{0,5}\{0,5\}
E−E^-R1R_1(0,1,2;3,5,4)(0,1,2;3,5,4)(0,3,4;2,1,5)(0,3,4;2,1,5)(0,5,3;4,1,2)(0,5,3;4,1,2)(0,2,5;1,3,4)(0,2,5;1,3,4){0,5}\{0,5\}——
E−E^-R3R_3(0,1,2;3,5,4)(0,1,2;3,5,4)(0,2,3;4,1,5)(0,2,3;4,1,5)(0,3,4;5,1,2)(0,3,4;5,1,2)(0,2,5;1,3,4)(0,2,5;1,3,4){0,2}\{0,2\}{0,3}\{0,3\}{0,4}\{0,4\}

Table 3 (PDF p. 15). Realisations of the seven patterns, in port order outside, forward, backward. A listed pair WijW_{ij} is exposed at both ends of the block on vivjv_iv_j; a dash denotes an unmarked edge. Colour normalisations are given in the proof.

The Heawood pole

When the core has no 4-cycle, Lemma 3.25 gives a Heawood closure HH with root rr, or the core is itself the Heawood graph. Since HH is det-extremal, any Pfaffian signing of HH differs from the all-positive signing on a cut [7 Corollary 4.3]. Thus on H−rH-r the marked edges are exactly those joining different values of a binary vertex function. Its values at the three neighbours of rr determine which smaller pole suffices for the replacement.

Lemma 3.27. Let HH be the Heawood graph, r∈V(H)r \in V(H) and s:V(H)∖{r}→{0,1}s: V(H) \setminus\{r\} \to\{0,1\}. Form a 3-pole RsR_s by replacing each edge uvuv of H−rH-r with s(u)≠s(v)s(u) \ne s(v) by one block BB. If ss is constant on NH(r)N_H(r), then RsR_s is an exact vertex simulator. Otherwise let xx be the unique neighbour with the minority value. Then RsR_s realises every ordered boundary-signature triple realised by a vertex with a single block BB on the arm corresponding to xx.

Proof. If the neighbours of rr have common value tt, extend ss by s(r)=ts(r)=t and put S=s−1(1)S=s^{-1}(1). No edge at rr is expanded in HδH(S)H_{\delta H(S)}. The matching-lift calculation in Lemma 3.22 shows that every perfect matching of the expanded graph projects to a perfect matching MM of HH and has sign

(−1)∣M∩δH(S)∣sgn⁡(M)=(−1)∣S∣sgn⁡(M).(-1)^{|M\cap\delta_H(S)|}\operatorname{sgn}(M)=(-1)^{|S|}\operatorname{sgn}(M).

Here ∣M∩δH(S)∣≡∣S∣(mod2)|M\cap\delta_H(S)|\equiv|S|\pmod2, since matching edges inside SS cover vertices in pairs. Thus HδH(S)H_{\delta H(S)} is det-extremal, as HH is. Deleting rr gives RsR_s, so Theorem 3.9 applies.

For the mixed case write HH in the cyclic model of Section 3.3:

V(H)={ai,bi:i∈Z7},E(H)={aibi+d:d∈{0,1,3}}.V(H)=\{a_i,b_i:i\in\mathbb{Z}_7\},\qquad E(H)=\{a_i b_{i+d}:d\in\{0,1,3\}\}.

Translations and ai↔b−ia_i\leftrightarrow b_{-i} give vertex transitivity. The vertex stabiliser acts as S3S_3 on its neighbours: in the Fano-plane model, every invertible map of a fixed two-dimensional subspace extends to the ambient three-dimensional space. We may therefore take r=b0,x=a0r=b_0,x=a_0 and, by complementing ss, assume s(a0)=1s(a_0)=1, s(a4)=s(a6)=0s(a_4)=s(a_6)=0. For the tables below, order the port set at arms bi,bi+1,bi+3b_i,b_{i+1},b_{i+3} and those at bib_i by increasing index in {0,…,6}\{0,\ldots,6\} of their aa-neighbours. Missing ports retain their positions, namely 0,2,10,2,1 at a0,a4,a6a_0,a_4,a_6.

Normalise the central state of the comparison pole, with the marked arm first, to (0,1,2;3,4,5)(0,1,2;3,4,5). Its direct-arm signatures are (1,{3,5})(1,\{3,5\}), (2,{3,4})(2,\{3,4\}); its other signature is (d,W)(d,W), where

d≠0,∣W∣=2,W∩{0,d,4,5}=∅.d\ne0,\qquad|W|=2,\qquad W\cap\{0,d,4,5\}=\varnothing.

The automorphism φ=(a2 a3)(a4 a6)(b2 b4)(b5 b6)\varphi=(a_2\ a_3)(a_4\ a_6)(b_2\ b_4)(b_5\ b_6), combined with the colour permutation ρ=(1 2)(4 5)\rho=(1\ 2)(4\ 5), fixes the minority arm and interchanges the majority arms while preserving their signatures. Its orbits on the nine possibilities are

{(1,{2,3}),(2,{1,3})},{(3,{1,2})},\{(1,\{2,3\}),(2,\{1,3\})\},\qquad\{(3,\{1,2\})\},
{(4,{1,2}),(5,{1,2})},{(4,{1,3}),(5,{2,3})},\{(4,\{1,2\}),(5,\{1,2\})\},\qquad\{(4,\{1,3\}),(5,\{2,3\})\},
{(4,{2,3}),(5,{1,3})}.\{(4,\{2,3\}),(5,\{1,3\})\}.

It suffices to realise the five representatives in Table 5. Assign to each vertex the state σv(s(v))\sigma_v(s(v)) in Table 4; dashes mark unused states and the three starred entries are supplied by Table 5. Each displayed state is a permutation of the palette. Direct substitution at every edge uvuv of H−rH-r gives endpoint signatures (c,P),(d,Q)(c,P),(d,Q) satisfying

(X,Y)(X,Y)P0P_0P1P_1P2P_2P3P_3
E+E^+(U,V)(U,V){3,4}\{3,4\}{1,5}\{1,5\}{4,5}\{4,5\}{1,2}\{1,2\}
E−E^-(V,U)(V,U){4,5}\{4,5\}{1,5}\{1,5\}{1,2}\{1,2\}{3,4}\{3,4\}

Table 4.

(d,W)(d,W)σa0(1)\sigma_{a_0}(1)σb1(1)\sigma_{b_1}(1)σb3(1)\sigma_{b_3}(1)
(1,{2,3})(1,\{2,3\})(1,0,4;5,2,3)(1,0,4;5,2,3)(0,4,5;3,1,2)(0,4,5;3,1,2)(4,5,1;2,3,0)(4,5,1;2,3,0)
(3,{1,2})(3,\{1,2\})(3,0,4;5,1,2)(3,0,4;5,1,2)(0,4,5;2,1,3)(0,4,5;2,1,3)(4,5,1;2,3,0)(4,5,1;2,3,0)
(4,{1,2})(4,\{1,2\})(4,0,3;5,1,2)(4,0,3;5,1,2)(0,4,5;2,1,3)(0,4,5;2,1,3)(3,5,1;2,4,0)(3,5,1;2,4,0)
(4,{1,3})(4,\{1,3\})(4,2,0;5,1,3)(4,2,0;5,1,3)(2,4,5;3,1,0)(2,4,5;3,1,0)(0,5,1;2,3,4)(0,5,1;2,3,4)
(4,{2,3})(4,\{2,3\})(4,1,0;5,2,3)(4,1,0;5,2,3)(1,4,5;3,2,0)(1,4,5;3,2,0)(0,5,1;2,3,4)(0,5,1;2,3,4)

Table 5. The three states depending on the boundary signature.

vvσv(0)\sigma_v(0)σv(1)\sigma_v(1)
a0a_0−-∗*
a1a_1(2,1;4,5,0,3)(2,1;4,5,0,3)(4,0,3;2,1,5)(4,0,3;2,1,5)
a2a_2(3,4,2;0,1,5)(3,4,2;0,1,5)(4,5,0;3,2,1)(4,5,0;3,2,1)
a3a_3(0,5,3;4,2,1)(0,5,3;4,2,1)(1,2,4;3,5,0)(1,2,4;3,5,0)
a4a_4(0,4,1;3,5,2)(0,4,1;3,5,2)−-
a5a_5(0,4,1;3,2,5)(0,4,1;3,2,5)(2,3,5;4,0,1)(2,3,5;4,0,1)
a6a_6(0,2,5;3,1,4)(0,2,5;3,1,4)−-
b1b_1(3,2,1;4,0,5)(3,2,1;4,0,5)∗*
b2b_2(1,3,5;4,0,2)(1,3,5;4,0,2)(0,4,2;5,1,3)(0,4,2;5,1,3)
b3b_3(2,4,0;3,5,1)(2,4,0;3,5,1)∗*
b4b_4(4,5,0;3,1,2)(4,5,0;3,1,2)(3,2,1;5,0,4)(3,2,1;5,0,4)
b5b_5(2,4,0;1,3,5)(2,4,0;1,3,5)(0,3,2;4,5,1)(0,3,2;4,5,1)
b6b_6(3,4,0;2,5,1)(3,4,0;2,5,1)(4,3,1;5,0,2)(4,3,1;5,0,2)

Table 4 (PDF p. 16). States common to all five cases.

c=d,P∩Q=∅,s(u)=s(v),c≠d,∣P∪Q∪{c,d}∣≤4,s(u)≠s(v).\begin{aligned} c&=d,\quad P\cap Q=\varnothing,\quad s(u)=s(v),\\ c&\ne d,\quad|P\cup Q\cup\{c,d\}|\le4,\quad s(u)\ne s(v). \end{aligned}

These are the direct-edge and single-block interface conditions. At each edge only its two endpoint values matter, so checking at most four pairs of states for each of the five representatives covers every assignment of the remaining ten values of ss. The boundary rows give exactly (d,W),(1,{3,5}),(2,{3,4})(d,W),(1,\{3,5\}),(2,\{3,4\}). The interface criterion completes the required colouring.

Completion of the bipartite proof

We are now ready to prove Theorem 1.1. In each case it remains to identify the smaller base, check that it is not the 3-bond, and apply the appropriate replacement.

Proof. Take a minimum counterexample G=PFG=PF as in Lemma 3.22. Suppose first that PP has a 4-cycle CC. By Lemma 3.23, k=∣F∩E(C)∣k=|F\cap E(C)| is one or three. The graph P−V(C)P-V(C) is connected, since each component would require at least three of the four edges leaving CC. Label CC so its expanded pole is R1R_1 or R3R_3. Delete that pole, retaining all blocks on edges leaving CC, and pair the free incidences as (v0,v1),(v2,v3)(v_0,v_1),(v_2,v_3). This gives a connected loopless cubic bipartite multigraph KK: each new edge joins opposite partition sets. Moreover P≠K3,3P\ne K_{3,3}, whose six signed determinant terms always have negative product (each matrix entry occurs twice), whereas six terms of a common sign have positive product. Hence ∣V(P)∣≥8|V(P)|\ge8 and

∣V(K)∣=∣V(P)∣−4+2(∣F∣−k)≥4.|V(K)|=|V(P)|-4+2(|F|-k)\ge4.

Thus K≠M0K\ne M_0 and ∣V(K)∣<∣V(G)∣|V(K)|<|V(G)|. Minimality gives a colouring of T(K)T(K). At each of the two new edges, the two endpoint signatures have a common colour and disjoint exposed pairs; these are precisely the data required by Lemma 3.26. Restoring the pole therefore gives a colouring of T(G)T(G), a contradiction.

Assume now that PP has no 4-cycle and is not Heawood. Lemmas 3.25 and 3.24 give a Heawood closure HH, rooted at rr, with a Pfaffian signing agreeing with FF on its non-root edges. Write its negative edges as a cut, with binary vertex function ss, as in the construction above. Replace the expanded shore by a vertex if ss is constant on NH(r)N_H(r), and otherwise by a vertex with one block on the minority arm. Retain all original blocks on cut edges, including any two consecutive blocks created by this operation. The new graph G′G' is connected, loopless, cubic and bipartite. The complementary closure RR of PP is simple cubic bipartite, so ∣V(G′)∣≥∣V(R)∣≥6|V(G')|\ge|V(R)|\ge6. Replacing the thirteen Heawood vertices and their internal blocks by at most three vertices gives ∣V(G′)∣<∣V(G)∣|V(G')|<|V(G)|. Minimality colours T(G′)T(G'); Lemma 3.27 then restores the shore with unchanged boundary signatures, a contradiction.

Finally let P=HP=H be the Heawood graph. Again FF is a non-empty cut: write F=δH(S)F=\delta_H(S) and s=1Ss=1_S. Choose rr incident with FF, of marked degree k∈{1,2}k\in\{1,2\}. Replace the expanded H−rH-r by its single-block comparison pole. If k=1k=1, its minority arm is the marked arm; the replacement gives two direct connections and a third through two blocks. The direct edges form another block, so this is a cycle of three blocks. If k=2k=2, its minority arm is unmarked, giving one block on each of three connections, the three-block theta. Propositions 2.4 and 3.21 colour these graphs, and Lemma 3.27 restores H−rH-r, a final contradiction. The lower bound (1) gives equality.

Claw-free cubic multigraphs

Let GG be a connected bridgeless cubic claw-free multigraph different from the 3-bond M0M_0. We prove Theorem 1.2 directly, whether or not GG has parallel edges. The block decomposition first identifies the chains of diamonds and parallel-edge blocks in GG. We then show which chains can be restored without changing the colours at their attachments. Only a single block BB needs to be coloured together with its neighbouring triangles.

From the base to its skeleton

In the simple case the following partition is the triangle-and-diamond decomposition underlying [16 Proposition 1]. In a multigraph, the blocks BB account for the vertices lying on no triangle.

Lemma 4.1. Suppose G≇K4G \not\cong K_4. The parallel-edge blocks BB, the induced diamonds and the triangles outside all diamonds partition V(G)V(G). Each block BB and each diamond has two edges leaving it, and each triangle block has three.

Proof. A triple edge would give the excluded component M0M_0. Thus each parallel pair forms a block BB, and these blocks are vertex-disjoint by cubicity. If both ends of a block BB had the same outside neighbour, the remaining edge at that neighbour would be a bridge. Hence no vertex of BB belongs to a triangle.

Every remaining vertex has three distinct neighbours. By claw-freeness, two of them are adjacent, so the vertex belongs to a triangle. Two distinct triangles that meet must share an edge, by cubicity. Their union induces a diamond or a K4K_4; the latter would be a whole component. Every triangle meeting an induced diamond lies inside it: its centres have no outside neighbours, and its two tips are nonadjacent and have only one outside edge each. Consequently, distinct diamonds are disjoint, as are the triangles outside them. Counting the unused incidences at each block gives its boundary size. □

Contract the blocks, discarding the edges internal to each block and retaining each edge between blocks with its original attachment vertices. Write JJ for the resulting multigraph. Its triangle vertices have degree three, and its other vertices have degree two.

Lemma 4.2. If GG has no triangle block, JJ is a cycle, possibly of length two. Otherwise the edges of JJ partition into paths between distinct triangle vertices, with all internal vertices of degree two. Replacing each path by one edge gives a connected loopless cubic multigraph QQ, the skeleton of GG. Replacing the corresponding chains in GG by edges between their attachment vertices gives a reduced base G0≅T(Q)G_0 \cong T(Q).

Proof. JJ is connected and bridgeless: a bridge between contracted blocks would lift to a bridge of GG. If every vertex has degree two, JJ is therefore a cycle. Otherwise follow the unique continuation through each degree-two vertex until reaching a triangle vertex. A trail returning to the triangle at which it started would leave only the third incidence at that triangle as a connection to the rest of JJ, contrary to bridgelessness. Thus the paths have distinct endpoints and their suppression produces a loopless cubic multigraph QQ.

Each retained triangle of GG now corresponds to a vertex of QQ. Its three attachment vertices are precisely the three incidences at that vertex, and each new joining edge connects the two incidences of one edge of QQ. This identifies the reduced graph with T(Q)T(Q), even when two paths give parallel edges of QQ. □

A direct edge between two triangle blocks represents a chain of length zero. For each non-empty chain, record its block sequence and both attachment vertices so that the reduction can be reversed. Figure 3 illustrates the operation for a chain of diamonds.

Suppression of a diamond chain in the base graph

Figure 3. Suppression of a diamond chain in the base graph. The two triangle blocks and their attachment vertices x,yx,y are retained, and the chain is replaced by an edge f=xyf=xy. The diamond chains and attachment ports are recorded. Unfinished edges continue to the rest of the base.

Colouring diamond chains and mixed chains

The decomposition tells us which chains have been suppressed. We now colour their truncations so that the chains can be put back at their recorded attachments. Regard a diamond as a 2-pole with one dangling half-edge at each tip.

The diamond can replace an edge without disturbing the colouring at either end. To see why, suppose that the edge to be replaced has colour cc and exposed pairs U,VU,V at its two ends. The diamond must expose a pair disjoint from UU at the first join and one disjoint from VV at the second. We can arrange for these pairs to be VV and UU, respectively, which also permits iteration.

Lemma 4.3. Let DD be a diamond with tips a,ba,b and centres u,vu,v. Let c∈Ωc \in\Omega, and let U,VU,V be disjoint 2-element subsets of Ω∖{c}\Omega\setminus\{c\}. Equip DD with one dangling half-edge at each tip. Its augmented truncation admits a strong edge-colouring with colours in Ω\Omega whose boundary signatures are

(c,V)at a,(c,U)at b.(c,V) \quad\text{at } a,\qquad(c,U) \quad\text{at } b.

Proof. Identify Ω\Omega with {1,2,3,4,5,6}\{1,2,3,4,5,6\}. Use the colouring in Table 6. The first ports at a,ba,b are the boundary ports.

Each row contains all six colours. The five internal interfaces of the 2-port piece are checked explicitly below:

base edgeexternal colourfirst exposed pairsecond exposed pair
auau44{6,3}\{6,3\}{5,1}\{5,1\}
avav55{6,2}\{6,2\}{4,1}\{4,1\}
bubu22{6,5}\{6,5\}{3,1}\{3,1\}
bvbv33{6,4}\{6,4\}{2,1}\{2,1\}
uvuv66{3,5}\{3,5\}{2,4}\{2,4\}

Table 7.

The external colours agree and the exposed pairs are disjoint at every interface, so Lemma 2.1 applies. The boundary signatures are (1,{2,3})(1,\{2,3\}) at aa and (1,{4,5})(1,\{4,5\}) at bb.

Choose a permutation of Ω\Omega taking 11 to cc, {2,3}\{2,3\} to VV, and {4,5}\{4,5\} to UU, and apply it to the table. The resulting colouring is strong and has the required signatures.

We can now use one copy of the same colouring for every diamond in a chain.

Lemma 4.4. Let KK be a loopless cubic multigraph, let φ\varphi be a strong edge-colouring of T(K)T(K) with colours in Ω\Omega, and let F⊆E(K)F \subseteq E(K). For each e∈Fe \in F, choose a positive integer kek_e, and form K′K' by replacing ee with a chain of kek_e diamonds. Then T(K′)T(K') admits a strong edge-colouring with colours in Ω\Omega that agrees with φ\varphi on every retained canonical triangle and on every external edge corresponding to an edge of E(K)∖FE(K) \setminus F.

Proof. At the endpoints x,yx,y of a replaced edge, write the old signatures as (c,U),(c,V)(c,U),(c,V). By Lemma 2.1 the pairs are disjoint and avoid cc. Orient the chain from xx to yy and use Lemma 4.3 on each diamond, with entry signature (c,V)(c,V) and exit signature (c,U)(c,U). At every join, including the first and the last, the colour is cc and the exposed pairs are U,VU,V. This preserves the state at each old port. The replacements therefore work simultaneously even when two chosen edges share an endpoint.

Figure 4 shows the local colouring and its repetition along a chain. Chains of length zero correspond to unreplaced edges.

A 2-port diamond colouring and the same boundary state on every diamond

Figure 4. (a) The 2-port diamond colouring of Table 6. Red numbers denote edge colours; open circles are auxiliary degree-1 endpoints. (b) Already coloured pieces are joined through the restored diamond pieces. Each diamond has entry signature (c,V)(c,V) and exit signature (c,U)(c,U), so every join compares the disjoint pairs U,VU,V, regardless of the chain length. For k=1k=1 there is one diamond; for k=0k=0 the end blocks are joined directly.

A closed chain in the block decomposition may contain both diamonds and copies of BB. The colouring above and the cycle of parallel-edge blocks from Section 2 handle all but one small case.

Proposition 4.5. Every cyclic arrangement of copies of BB and diamond 2-poles, other than the closure M0M_0 of one copy of BB, has a truncation of strong chromatic index six.

Proof. For the explicit colourings take Ω={1,2,3,4,5,6}\Omega= \{1,2,3,4,5,6\}. If there are no blocks BB, orient the cycle and use the diamond colouring of Table 6 on every block, with entry signature (1,{2,3})(1,\{2,3\}) and exit signature (1,{4,5})(1,\{4,5\}). Every join is compatible, including the closing one. For one diamond, joining its tips gives K4K_4.

If there are at least two copies of BB, suppress the intervening diamond chains. Proposition 2.4 colours the truncation of the resulting cycle of blocks BB, and Lemma 4.4 restores the suppressed chains with all retained states fixed.

It remains to treat one BB and at least one diamond. For one of each, take a diamond with tips a,ba,b and centres u,vu,v, parallel edges p,qp,q between x,yx,y, and joins ax,byax,by. The following states give compatible interfaces:

VertexOrdered portsLocal state
aa(out,u,v)(\mathrm{out},u,v)(1,4,5;6,2,3)(1,4,5;6,2,3)
bb(out,u,v)(\mathrm{out},u,v)(1,2,3;6,4,5)(1,2,3;6,4,5)
uu(a,b,v)(a,b,v)(4,2,6;3,5,1)(4,2,6;3,5,1)
vv(a,b,u)(a,b,u)(5,3,6;2,4,1)(5,3,6;2,4,1)

Table 6. A strong 6-edge-colouring of the 2-port truncation of a diamond. The signatures at its two outside ports are (1,{2,3})(1,\{2,3\}) and (1,{4,5})(1,\{4,5\}).

vertexport orderstate
aa(u,v,x)(u,v,x)(1,2,3;4,5,6)(1,2,3;4,5,6)
bb(u,v,y)(u,v,y)(2,6,4;5,3,1)(2,6,4;5,3,1)
uu(a,b,v)(a,b,v)(1,2,5;6,3,4)(1,2,5;6,3,4)
vv(a,b,u)(a,b,u)(2,6,5;4,1,3)(2,6,5;4,1,3)
xx(p,q,a)(p,q,a)(6,5,3;2,1,4)(6,5,3;2,1,4)
yy(p,q,b)(p,q,b)(6,5,4;1,2,3)(6,5,4;1,2,3)

Table 6 (PDF p. 19).

Lemma 4.4 inserts any further diamonds. The local lower bound (2.1) gives equality in all cases.

To insert a chain in place of an edge of KK, we apply Lemma 2.2 to that edge and the edge used to close the chain. Only the colours on the closed chain need to be permuted, so the local states on KK stay fixed.

Corollary 4.6. Let KK be a loopless cubic multigraph with a strongly 6-edge-coloured truncation. Replacing an edge of KK by a non-empty chain of copies of BB and diamonds preserves this colourability, with all retained local states and all other external colours fixed, unless the chain consists of a single BB.

Proof. If the chain is not a single BB, closing it by an edge gives a base other than M0M_0. Proposition 4.5 colours its truncation. The gluing described above now inserts the chain. A single BB cannot preserve both endpoint states because its two boundary colours must differ, whereas a direct edge has one common colour.

Colouring the triangles and the single parallel-edge blocks

For a connected loopless cubic multigraph QQ and F⊆E(Q)F \subseteq E(Q), let GFG_F be obtained from T(Q)T(Q) by inserting a block BB into the external edge corresponding to each e∈Fe \in F. Thus G∅=T(Q)G_{\varnothing}=T(Q). For the base GG above, FF will consist precisely of the edges of its skeleton that represent a single BB. In this construction itself QQ need not be bridgeless.

In T(GF)T(G_F) each triangle of T(Q)T(Q) contributes a piece XX on nine vertices, one canonical triangle for each vertex of the original triangle. It has three outside ports; attaching a pendant edge to each gives its augmented truncation. In Figure 5 the three canonical triangles are p0p1p2p_0p_1p_2, p3p5p6p_3p_5p_6 and p4p7p8p_4p_7p_8, with outside ports p0,p5,p8p_0,p_5,p_8.

Figure 5. The 9-vertex piece XX, with ports p0p_0, p5p_5, p8p_8 shown as open circles. Dashed segments represent the three interblock edges.

We use the same palette Ω={1,2,3,4,5,6}\Omega=\{1,2,3,4,5,6\} throughout this construction. The following property of XX lets us adapt a boundary colour to a neighbouring block without changing the exposed pair.

Lemma 4.7. Fix two colours a,b∈Ωa,b \in\Omega and a two-element set W⊆Ω∖{a,b}W \subseteq\Omega\setminus\{a,b\}, with a≠ba \ne b. Any assignment of colours from {a,b}\{a,b\} to the three outside ports of XX extends to a strong 6-edge-colouring of the augmented piece with exposed pair WW at every outside port.

Proof. Up to permuting colours and ports, take W={4,5}W=\{4,5\} and prescribe (1,1,t)(1,1,t) with t∈{1,2}t \in\{1,2\}. Let t′t' be the other element of {1,2}\{1,2\}. List the vertices of the base triangle in cyclic order, and at each vertex order the ports as outside, next, previous. Use the following three local states in that cyclic order:

(1,2,3;6,5,4),(1,6,2;3,5,4),(t,3,6;t′,5,4).(1,2,3;6,5,4), \qquad(1,6,2;3,5,4), \qquad(t,3,6;t',5,4).

Each outside port exposes {4,5}\{4,5\}. The three joins have colours 2,6,32,6,3, respectively. The pairs across them are {6,4},{3,5}; {3,4},{t′,5};\{6,4\},\{3,5\};\ \{3,4\},\{t',5\}; and {t′,4},{6,5}\{t',4\},\{6,5\}, respectively. Each pair is disjoint from its partner, so Lemma 2.1 gives the required colouring.

For completeness, the same triangle piece also admits a mixed prescription with different exposed pairs. If a,b,γa,b,\gamma are distinct, the two ports of colour aa may expose {b,γ}\{b,\gamma\} and the port of colour bb may expose {a,γ}\{a,\gamma\}. In the same cyclic port order, the states

(2,3,5;6,4,1),(1,6,3;5,4,2),(1,5,6;3,4,2)(2,3,5;6,4,1), \qquad(1,6,3;5,4,2), \qquad(1,5,6;3,4,2)

give this prescription for (a,b,γ)=(1,2,4)(a,b,\gamma)=(1,2,4), with boundary colours (2,1,1)(2,1,1). At the three joins the pairs are {6,1},{5,4}; {5,2},{3,4};\{6,1\},\{5,4\};\ \{5,2\},\{3,4\}; and {3,2},{6,4}\{3,2\},\{6,4\}. They are disjoint at each join; permuting colours and ports gives the stated prescription.

Lemma 2.1 also applies when whole pieces are joined: given strong colourings of the augmented pieces, replacing each pair of corresponding pendant edges by its joining edge gives a strong colouring if and only if their boundary colours agree and their exposed pairs are disjoint. Indeed, these joins are the only new interfaces between canonical triangles. Across a marked edge the two triangle pieces instead connect to opposite ends of BB: their boundary colours must differ, and the block needs a pair disjoint from the two exposed pairs and both boundary colours (Proposition 2.3). The next construction meets both requirements at once.

Proposition 4.8. If D=(V(Q),E(Q)∖F)D=(V(Q),E(Q)\setminus F) has a proper 3-vertex-colouring, then χ′(T(GF))=6\chi^\prime(T(G_F))=6.

Proof. Partition the palette into pairs U={u,u′}U=\{u,u^\prime\}, V={v,v′}V=\{v,v^\prime\}, Z={z,z′}Z=\{z,z^\prime\}. Fix representatives u,v,zu,v,z once and use U,V,ZU,V,Z as the three vertex colours of DD. Prescribe at every port of a triangle piece the exposed pair assigned to its vertex. For each edge of QQ choose the boundary colours as in the table, up to permuting the pairs together with their fixed representatives.

edge of QQendpoint pairsboundary colourspair on BB
e∉Fe\notin FU,VU,Vz,zz,z—
e∈Fe\in FU,VU,Vv,uv,uZZ
e∈Fe\in FU,UU,Uv,zv,z{v′,z′}\{v^\prime,z^\prime\}

Table 1 (PDF p. 21).

The first row covers every unmarked edge because the colouring of DD is proper. In the last row the choice of which endpoint receives vv is immaterial. All boundary colours at a piece assigned UU lie in {v,z}\{v,z\}, so Lemma 4.7 realises the three prescriptions simultaneously; the same holds for VV and ZZ. Unmarked interfaces are compatible by the first row. On each marked edge the common pair on BB avoids both boundary colours and is disjoint from both endpoint pairs. Proposition 2.3 therefore supplies the block colouring, and Lemma 2.1 gives a strong colouring of the assembled truncation. The lower bound is (1).

We explain why this construction needs just one further certificate. If F≠∅F\ne\varnothing, every component of DD contains a vertex incident in QQ with an edge of FF, since QQ is connected. This vertex has degree at most two in DD. Root a spanning tree of the component there and colour vertices in nonincreasing order of depth. Each non-root vertex still has its parent uncoloured when its turn comes, and the root has at most two neighbours. Thus three colours always suffice. If F=∅F=\varnothing, the underlying simple graph of QQ is connected of maximum degree at most three. By Brooks’ theorem [3] it too has a proper 3-vertex-colouring, unless it is K4K_4 (paths and cycles also admit three colours). In the latter case cubicity forces Q=K4Q=K_4 itself. This leaves G∅=T(K4)G_{\varnothing}=T(K_4).

Proposition 4.9. Let G0=T(K4)G_0=T(K_4). Then T(G0)T(G_0) admits a strong 6-edge-colouring.

Proof. Label the vertices of G0G_0 by 0,…,110,\ldots,11 so that its four triangle blocks have vertex sets

{0,1,2},{3,4,5},{6,7,8},{9,10,11},\{0,1,2\},\quad\{3,4,5\},\quad\{6,7,8\},\quad\{9,10,11\},

and the six edges between these triangles are

03,16,29,47,5 10,8 11.03,\quad16,\quad29,\quad47,\quad5\,10,\quad8\,11.

For a vertex qq of G0G_0, list its neighbours in increasing order as (q1,q2,q3)(q_1,q_2,q_3). Use the local states in Table 7 to colour T(G0)T(G_0), with the ports at each vertex in this order.

In every row, the two colour triples together contain exactly 1,…,61,\ldots,6. The external colours agree at both endpoints of every edge of G0G_0, so the colouring is well-defined. Each exposed pair Pq(qqi)P_q(qq_i) is obtained by deleting hq(qqi)h_q(qq_i) from the opposite internal triple. All eighteen interfaces are listed below; each edge qrqr is specified by its two vertex labels.

eePq(e)P_q(e)Pr(e)P_r(e)eePq(e)P_q(e)Pr(e)P_r(e)
01{4,6}\{4,6\}{1,3}\{1,3\}02{5,6}\{5,6\}{1,4}\{1,4\}
03{4,5}\{4,5\}{2,3}\{2,3\}12{3,6}\{3,6\}{2,4}\{2,4\}
16{1,6}\{1,6\}{2,3}\{2,3\}29{1,2}\{1,2\}{3,5}\{3,5\}
34{2,6}\{2,6\}{1,3}\{1,3\}35{3,6}\{3,6\}{1,4}\{1,4\}
45{3,5}\{3,5\}{4,6}\{4,6\}47{1,5}\{1,5\}{3,4}\{3,4\}
510{1,6}\{1,6\}{2,5}\{2,5\}67{2,6}\{2,6\}{3,5}\{3,5\}
68{3,6}\{3,6\}{1,4}\{1,4\}78{4,5}\{4,5\}{1,3}\{1,3\}
811{3,4}\{3,4\}{1,5}\{1,5\}910{3,4}\{3,4\}{5,6}\{5,6\}
911{4,5}\{4,5\}{1,3}\{1,3\}1011{2,6}\{2,6\}{3,5}\{3,5\}

Table 2 (PDF p. 21).

Every displayed pair of sets is disjoint, so Lemma 2.1 gives the required strong colouring.

qq(q1,q2,q3)(q_1,q_2,q_3)Local state
0(1,2,3)(1,2,3)(2,3,1;5,4,6)(2,3,1;5,4,6)
1(0,2,6)(0,2,6)(2,5,4;6,1,3)(2,5,4;6,1,3)
2(0,1,9)(0,1,9)(3,5,6;2,1,4)(3,5,6;2,1,4)
3(0,4,5)(0,4,5)(1,4,5;6,3,2)(1,4,5;6,3,2)
4(3,5,7)(3,5,7)(4,2,6;5,1,3)(4,2,6;5,1,3)
5(3,4,10)(3,4,10)(5,2,3;6,1,4)(5,2,3;6,1,4)
6(1,7,8)(1,7,8)(4,1,5;6,3,2)(4,1,5;6,3,2)
7(4,6,8)(4,6,8)(6,1,2;5,4,3)(6,1,2;5,4,3)
8(6,7,11)(6,7,11)(5,2,6;3,4,1)(5,2,6;3,4,1)
9(2,10,11)(2,10,11)(6,1,2;4,5,3)(6,1,2;4,5,3)
10(5,9,11)(5,9,11)(3,1,4;6,2,5)(3,1,4;6,2,5)
11(8,9,10)(8,9,10)(6,2,4;3,5,1)(6,2,4;3,5,1)

Table 7 (PDF p. 22). A complete local-state certificate for T(G0)T(G_0) when G0=T(K4)G_0=T(K_4).

Lemma 4.10. For every connected loopless cubic multigraph QQ and every F⊆E(Q)F \subseteq E(Q), the graph GFG_F satisfies

χs′(T(GF))=6.\chi^\prime_s(T(G_F))=6.

Proof. The preceding argument gives a proper 3-vertex-colouring of Q−FQ-F in every case except F=∅F=\varnothing and Q=K4Q=K_4. Apply Proposition 4.8 in the first case, and Proposition 4.9 and (1) in the exceptional case.

Restoring the chains and double truncations

We are now ready to prove Theorem 1.2. When triangle blocks are present, Lemma 4.10 colours them together with the chains consisting of a single parallel-edge block. The remaining chains can then be restored without changing any retained state.

Proof. For G=K4G=K_4, close a single diamond by joining its tips and apply Proposition 4.5. Otherwise form the block partition of Lemma 4.1. If it has no triangle block, the base is a cycle of diamonds and blocks BB by Lemma 4.2, so Proposition 4.5 again applies.

If there is a triangle block, Lemma 4.2 gives the reduced base T(Q)T(Q). Mark the edges FF of QQ that represent a single BB. Lemma 4.10 colours T(GF)T(G_F), so these blocks are already in place. Each remaining non-empty chain can be restored by Corollary 4.6 while preserving all retained states. The resulting strong 6-edge-colouring of T(G)T(G) attains the lower bound (1).

Bridgelessness was needed to identify the skeleton of a general claw-free base. When the base already has a partition into triangles, the colouring construction does not need this assumption.

Corollary 4.11. If the vertices of a simple cubic graph G0G_0, not necessarily connected, admit a partition into triangles, then χs′(T(G0))=6\chi^\prime_s(T(G_0))=6. In particular, every loopless cubic multigraph QQ satisfies

χs′(T(T(Q)))=6,\chi^\prime_s(T(T(Q)))=6,

including when QQ has bridges or is disconnected.

Proof. Contract the triangles of G0G_0, keeping the joining edges with their incidences. Each vertex of a triangle has precisely one edge leaving it, so the result is a loopless cubic multigraph QQ with G0≅T(Q)G_0\cong T(Q). On every component of QQ use Lemma 4.10 with F=∅F=\varnothing and reuse the palette between components. Conversely, the canonical triangles give the required partition for every base of the form T(Q)T(Q). When QQ is bridgeless, its truncation is also bridgeless and claw-free, so the double-truncation statement follows as well by applying Theorem 1.2 to each component of T(Q)T(Q).

Concluding remarks

The strong chromatic index of T(G)T(G) is six for connected cubic bipartite multigraphs and for connected bridgeless cubic claw-free multigraphs, with the sole exception of the 3-bond M0M_0 (Theorems 1.1 and 1.2). Its truncation is the triangular prism and has strong chromatic index nine. In the bipartite case the matchings of opposite signs give a direct colouring. The remaining det-extremal bases require a distinction: the structural description handles simple bases, and the marked-core argument handles parallel edges. In the claw-free case one block decomposition treats both kinds of base.

Corollary 4.11 also gives a result for bases with bridges: χs′(T(T(Q)))=6\chi'_s(T(T(Q))) = 6 for every loopless cubic multigraph QQ, since the canonical triangles partition the vertices of T(Q)T(Q).

Beyond the bipartite and claw-free classes, the multigraph form of Kardoš’s question remains open:

Does every connected loopless bridgeless cubic multigraph G≇M0 satisfy χs′(T(G))=6?\text{Does every connected loopless bridgeless cubic multigraph } G \not\cong M_0 \text{ satisfy } \chi'_s(T(G)) = 6?

References

  1. [1]L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992), 231–252.DOI
  2. [2]J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, London, 2008.
  3. [3]R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.
  4. [4]M. Choi, H. Kwon and B. Park, Det-extremal cubic graphs and the total domatic number, preprint, arXiv:2609.33902v1 (2026). https://arxiv.org/abs/2609.33902v1.
  5. [5]P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math. 72 (1988), 81–92.
  6. [6]J.-L. Fouquet and J.-L. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin. 16-A (1983), 141–150.
  7. [7]M. Funk, B. Jackson, D. Labbate and J. Sheehan, Det-extremal cubic bipartite graphs, J. Graph Theory 44 (2003), 50–64.DOI
  8. [8]P. Hall, On representatives of subsets, J. London Math. Soc. s1-10 (1935), 26–30.
  9. [9]Z. Han and Q. Cui, A note on strong edge-coloring of claw-free cubic graphs, J. Appl. Math. Comput. 69 (2023), 2503–2508.DOI
  10. [10]P. Horák, He Qing and W. T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993), no. 2, 151–160.DOI
  11. [11]F. Kardoš, Strong edge coloring of claw-free cubic graphs, in A. Onderko (ed.), Open problems of the 33rd Workshop on Cycles and Colourings, arXiv:2511.02892v1 (2025), Section 4, Problem 4.1, p. 5. https://arxiv.org/abs/2511.02892v1.
  12. [12]F. Kardoš, Private communication clarifying the intended bridgeless formulation of Problem 4.1 of the 33rd Workshop on Cycles and Colourings.
  13. [13]Y. Lin and W. Lin, The tight bound for the strong chromatic indices of claw-free subcubic graphs, Graphs Combin. 39 (2023), Article 58.arxiv.org/abs/2207.10264
  14. [14]J.-B. Lv, J. Li and X. Zhang, On strong edge-coloring of claw-free subcubic graphs, Graphs Combin. 38 (2022), Article 63.DOI
  15. [15]W. McCuaig, Even dicycles, J. Graph Theory 35 (2000), 46–68.
  16. [16]S.-il. Oum, Perfect matchings in claw-free cubic graphs, Electron. J. Combin. 18 (2011), no. 1, Paper P62.DOI
  17. [17]K. R. Tanwar, A diamond-free claw-free cubic graph with strong chromatic index 7, preprint, arXiv:2607.23462v1 (2026). https://arxiv.org/abs/2607.23462v1.
  18. [18]R. Thomas, A survey of Pfaffian orientations of graphs, in Proc. Int. Congr. Math. (Madrid, 2006), vol. III, Eur. Math. Soc., Zürich, 2006, 963–984.

Paper details

vlnc:W_yzuygagd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents