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 is obtained by replacing each vertex of a graph 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 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 -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 for the set of edges incident with and for the edge cut determined by . The term -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 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 , denoted by .
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 has strong chromatic index at most ; 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 , and a diamond is a graph isomorphic to 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 be a loopless cubic multigraph. Its truncation has a vertex for each incidence of a vertex with an edge . The three vertices associated with induce a triangle , called a canonical triangle. For every edge of , the graph has the edge . Edges within canonical triangles are called internal, and the edges corresponding to are called external. The vertex is the port of at . In particular, parallel edges of have distinct ports, and is a simple cubic graph that is both claw-free and diamond-free.
Han and Cui [9] proved that truncations of the prisms , for every , 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 satisfy ?
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 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 .
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 be a connected loopless cubic bipartite multigraph other than . Then .
Theorem 1.2. Let be a connected loopless bridgeless cubic claw-free multigraph other than . Then .
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 which is treated directly. Where triangle blocks remain, the graph obtained by suppressing the intervening chains is a truncation . Colouring its triangle pieces and restoring the chains gives the desired colouring of . The same construction yields the double-truncation corollary, which does not require 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 be a loopless cubic multigraph. The three edges of any canonical triangle and the three external edges incident with its ports are pairwise in strong conflict. Consequently,
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 of six colours. The labels of these colours may vary between constructions. A local state at assigns distinct colours to the three internal edges of and its three incident external edges. Write for the external colour at the port of . Let be the set of internal colours, the complement in of the three external colours. For , let be the colour of the internal edge opposite the port . Thus and map bijectively onto the external and internal colour sets, respectively. The two colours on internal edges incident with forms its exposed pair
The pair 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 , we write the state as , where and . 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 be a loopless cubic multigraph, let be a set of six colours, and let be a local state at each vertex . These states define a strong edge-colouring of with colour set if and only if, for every edge ,
Equivalently, let be a proper edge-colouring and, for each , let be a bijection, where . The assignments and define a strong edge-colouring of if and only if
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 , the corresponding external edge has the same colour at both ends, so . It joins the ports and , so every internal edge incident with the first is in strong conflict with every internal edge incident with the second. Thus , 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
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.
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.

Figure 1. The boundary data at an external edge corresponding to . The exposed pairs are and . Their disjointness is the compatibility condition. The opposite internal colours are and .
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 and be disjoint loopless cubic multigraphs, and suppose that both and admit strong 6-edge-colourings. Choose edges and , and let be obtained from by deleting and adding . Then admits a strong 6-edge-colouring. Given colourings of and , the construction may keep the local states on fixed and apply a single permutation of the six colours to those on .
Proof. Let be the external colour at , and let be its exposed pairs at . These are disjoint 2-element sets avoiding . Hence and the remaining singleton partition the six colours. Denote the corresponding data at by , where is exposed at and at .
Permute the colours of so that maps to , to , to , and the remaining colour to the remaining colour. Assign to both new external edges. On the exposed pairs are , and on they are again . The two new interfaces are therefore compatible. All local states agree with those in and the relabelled , so Lemma 2.1 applies.
Parallel-edge blocks
The parallel-edge block 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 are exactly
Proof. Write and . In the port order outside, first parallel edge, second parallel edge, the states
give the required signatures and compatible parallel interfaces. Conversely, let 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 are distinct, and are four distinct colours. The internal palettes are and . At each parallel interface, its two opposite colours must cover both . Since opposite colours at different ports of a vertex are distinct, each vertex uses opposite its parallel ports. Its boundary exposed pair is consequently , as required.
Joining copies of in a cycle gives the boundary prescriptions that we shall also use for bipartite 2-poles. The closure of a single copy is , so we start with two copies.
Proposition 2.4. If is a cyclic arrangement of copies of , then .
Proof. Number the blocks in cyclic order and let join to , with indices modulo . Take , and as exposed pairs. For even , alternate around the cycle and colour the joins alternately . For odd , alternate on and assign to . Colour alternately 5, 6, starting with 5, and give 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 be a connected loopless cubic bipartite multigraph with partition sets and . The proof of Theorem 1.1 starts with the signs of the perfect matchings of . If both signs occur, a binary assignment on gives a colouring of 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 is cubic and bipartite, 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
We call the values of 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 .
Fix orders on and . A perfect matching determines a bijection , whose sign is denoted by . 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 be a bipartite multigraph with a perfect matching, and fix linear orders on its two partition sets. We call det-extremal if all its perfect matchings have the same sign.
This property is independent of the orders. Let 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 is det-extremal if and only if ; see [7] for simple graphs.
Lemma 3.2. Let be a bipartite multigraph with a perfect matching , and let be an -alternating cycle of length . Then
Here denotes symmetric difference. Moreover, is not det-extremal if and only if some perfect matching of admits an alternating cycle whose length is divisible by four.
Proof. Switching along induces an -cycle on the matched images of , so the matching sign is multiplied by . For 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 to 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 be a connected loopless cubic bipartite multigraph with partition sets and , and let be a perfect matching, where and . Let be the digraph with vertex set and an arc for every edge . Then is strongly connected. Contracting the edges of induces a correspondence between -alternating cycles of length in and directed cycles of length in .
Proof. Every vertex of 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 expands to the alternating cycle with edges and , with indices modulo . Conversely, contracting the matching edges of an alternating cycle gives a directed cycle, oriented by its nonmatching edges from to . 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 sees both bits. For simple graphs the equivalence below is the bipartite formulation of [4 Theorem 3.5]. Indeed, take as the vertex set of a hypergraph and the neighbourhoods , indexed by , as its hyperedges. Its incidence graph is , 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 be a connected loopless cubic bipartite multigraph with partition sets and . Then is not det-extremal if and only if there exists a map such that
Proof. Suppose that is not det-extremal. By Lemma 3.2, choose a perfect matching and an -alternating cycle whose length is divisible by four. We construct from these data. By Lemma 3.3, the corresponding cycle in has even length. Assign alternating bits to its vertices . Whenever an arc has an assigned tail and an unassigned head, extend the assignment by setting . Strong connectivity guarantees that this procedure reaches all vertices. Each vertex has a predecessor on the initial cycle or in this extension with . Since both and are neighbours of , every neighbourhood in contains both bits.
Conversely, fix a perfect matching . For each , choose an incoming arc such that ; such an arc exists because 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 is not det-extremal.
Use the colour set
and index the ports at each vertex by their types. Thus is the external colour at the type- port, is the colour of the opposite internal edge, and . 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 . At a vertex in , 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 be a connected loopless cubic bipartite multigraph with partition sets and , let be a proper edge-colouring, and let satisfy for every . For an edge of type with endpoint , set
At , put
At let be the other endpoint of its type- edge and set . The vertices need not be distinct. The triple has a unique minority coordinate, namely the position of the bit that occurs once. Let fix this coordinate and interchange the other two. Put
Then these assignments define a strong 6-edge-colouring of .
Proof. At each , the external and internal palettes are and . At each , 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 of type , the intersection of its internal palettes is
If is the minority coordinate, this intersection is , and its colour is opposite the edge at both ends. Otherwise, let be the other majority coordinate. The intersection is . Its first colour is opposite the edge at , and its second is opposite the edge at , since . Thus (3) holds on every edge, and Lemma 2.1 completes the proof.
Example 3.6. If the neighbour bits at are , then
| port | 0 | 1 | 2 |
Here 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 and the proper edge-colouring may be chosen independently. Combining the preceding lemmas gives the first part of the bipartite result.
Corollary 3.7. Let be a connected loopless cubic bipartite multigraph that is not det-extremal. Then .
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 mixed. Removing one vertex from changes the task: we require mixed neighbourhoods only at the remaining vertices of , and the three new boundary signatures must reproduce a prescribed local state. The following construction achieves both requirements.
For a loopless cubic multigraph and , write for the 3-pole obtained by deleting and retaining its three incident half-edges. Its port signatures refer to the retained endpoints, as in § 2.
Definition 3.8. Let be a cubic 3-pole. We call an exact vertex simulator if, for every ordering of its three ports and every choice of six distinct colours , its augmented truncation admits a strong edge-colouring with these six colours whose port signatures, in the prescribed order, are
These are the signatures of a canonical triangle with state . 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 be a connected loopless cubic bipartite det-extremal multigraph, and let . Then the 3-pole 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 , and a perfect matching with . By Lemmas 3.3 and 3.2, is strongly connected and every directed cycle in is odd. Choose an outgoing spanning arborescence rooted at : a spanning directed tree with a unique directed path from to each vertex. Loops do not enter the tree. Set if the path from to in has even length, and otherwise. For every , its predecessor in satisfies , and are both neighbours of . Hence for all .
For each incoming arc , the tree path from to followed by that arc is a directed cycle, including the loop itself when . Its odd length forces to have even tree depth. Since , it follows that
Thus only the deleted vertex has a monochromatic neighbourhood in . After deletion each retained vertex of satisfies the mixed-bit condition, and the three incidences at retain distinct types even when they have the same neighbour. Choose a proper 3-edge-colouring of and apply (3.1)--(3.3) to . The proof of Lemma 3.5 verifies every ordinary interface. By (3.5), the signatures of the dangling ports, indexed by their types, are
Name the three types at according to the prescribed port order. Relabelling as and as gives (8).
Lemma 3.10. Let be a loopless cubic multigraph, let be a strong 6-edge-colouring of , and let . Let be an exact vertex simulator, and let be obtained by replacing with according to any bijection between the three incidences at and the three ports of . Then admits a strong 6-edge-colouring that agrees with outside the replacement.
Proof. Write the local state at , in attachment order, as . Realise (8) in the simulator. The new signatures equal the old ones at , 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 of a cubic multigraph , write for the 2-pole retaining a dangling half-edge at each endpoint of the deleted edge. When is connected, bipartite and det-extremal, this pole realises every boundary prescription of the double-edge block.
Corollary 3.11. Let . For each , let be a connected loopless cubic bipartite det-extremal multigraph and let . If is obtained by joining disjoint copies of the 2-poles cyclically, then .
Proof. For any connected loopless cubic bipartite det-extremal multigraph and any edge incident with , the 2-pole 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 from Theorem 3.9. Assign the port corresponding to to the outside port of the replaced vertex. The unreplaced vertex of the block takes the role of : its two non-boundary edges restore the other two incidences of . The resulting pole is therefore , with a dangling half-edge at each endpoint of . The replacement preserves the prescribed boundary signatures by the interface criterion.
Apply this observation to every , using the boundary prescriptions for a cycle of 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 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 at vertices is obtained by deleting and joining their neighbour sets by a bijection. If 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 be a simple 3-connected cubic bipartite graph. Then 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 be the Heawood graph with vertices , indexed by , and edges
Give these edges types 0, 1, 2, respectively. At the port order is ; at it is . This specifies a proper edge-colouring by types.
Lemma 3.13. Let be the Heawood graph. Then admits a strong 6-edge-colouring.
Proof. Assign the states in Table 1, using colours and the port orders above. The corresponding colouring is shown in Figure 2.
| State at | State at | |
| 0 | ||
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 |
Table 1. A complete 6-colour state assignment for the Heawood graph.

Figure 2. A strong 6-edge-colouring of in the classical circular layout of the Heawood graph. Clockwise from the top, the canonical triangles follow the Hamiltonian cycle ; the seven chords correspond to the edges . Red numerals are the edge colours 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 and define
Table 2 lists for all 21 edges. Each first set is contained in the second, as required. The result follows from Lemma 2.1.
| type 0 | type 1 | type 2 | |
| 0 | |||
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
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 and be disjoint simple 3-connected cubic bipartite graphs, and let and . Every vertex-sum of and at and is a simple 3-connected cubic bipartite graph.
Proof. Simplicity, cubicity and bipartiteness are immediate. Let contain at most two vertices of the vertex-sum. If meets each side in at most one vertex, both sides remain connected by the 3-connectivity of , and at least one joining edge survives. Otherwise, by symmetry, . The side remains connected. Every component of contains a surviving neighbour of , since otherwise it would be separated from in . Each such component therefore has a joining edge to . Thus deletion of 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 be a simple 3-connected cubic bipartite det-extremal graph. Then admits a strong 6-edge-colouring, which can be constructed from a vertex-sum expression for in terms of Heawood graphs.
Proof. By Theorem 3.12, 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 at , colour by induction and replace by . We need only the colouring on the side: the pole is assigned the signatures of the removed triangle at . 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 , its shores are and . 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 . 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 be a connected loopless cubic bipartite multigraph with partition sets and . Then the following statements hold.
is bridgeless and has no cut vertex.
For every 2-edge cut, each shore induces a connected subgraph and contains equally many vertices of and . Its two boundary endpoints are distinct and belong to opposite partition sets, so its closure is a connected loopless cubic bipartite multigraph.
If is simple, then 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 and for the numbers of edges leaving at vertices of and , respectively. Counting degrees gives
A bridge would make the right-hand side . 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 , the identity forces and . 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 is simple and deleting disconnects . Each resulting component has at least two boundary edges. If none has exactly two, there are exactly two components , each with three boundary edges, and is not an edge. Neither nor is a cut vertex, so both have neighbours in both components. Renaming if necessary, has two edges to and one to , and then 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 . Finally, simplicity of 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 , 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 : a connected multigraph whose blocks are cycles, including cycles of length two.
At a vertex of , start with the subgraph induced by its class. For each pair of edges incident with that forms a 2-edge cut of , add a marker between their endpoints in that class. The resulting piece 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 has degree two in the cactus.
Theorem 3.17. Let be a simple cubic bipartite det-extremal graph of connectivity two, with decomposition cactus and pieces as above. If , then 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 be a connected simple cubic bipartite det-extremal graph with vertex connectivity two. Then has a 2-edge cut with simple closures such that is 3-connected and det-extremal, whereas is not det-extremal.
Proof. The decomposition cactus has at least two vertices, since has connectivity two. Choose an end cycle of , that is, a cycle containing at most one cut vertex, and let be a non-cut vertex on it. Then . Its class therefore has exactly two boundary edges, and the piece is the closure of with exactly one marker. Theorem 3.17 makes det-extremal. If were a 3-bond, its two nonmarker edges would be parallel edges of , contradicting simplicity. The description of the pieces therefore makes simple and 3-connected.
Let be the other closure. By Lemma 3.16, both closures are connected cubic bipartite multigraphs. Write their markers as in and in , so that is obtained by deleting and adding . Choose perfect matchings of avoiding and containing , respectively, and of avoiding and containing . Such matchings exist because each closure admits a proper 3-edge-colouring. Let and be the cycles containing the markers in and , respectively. Cycles of length two are allowed in . Since is det-extremal, Lemma 3.3 gives .
Joining the paths and with gives a cycle in of length . It is alternating with respect to the perfect matching
Indeed, the two joining edges belong to , and each path alternates with its first and last edges outside . Since is det-extremal, another application of Lemma 3.2 yields
This holds for every choice of as above. If were parallel to an old edge , choose containing and put . Then would have length two, a contradiction. By Lemma 3.16, every possible pair of parallel edges in contains its marker, so is simple. Finally, is an -alternating cycle of length divisible by four. Lemma 3.2 therefore shows that is not det-extremal.
Theorem 3.19. Let be a connected simple cubic bipartite graph. Then .
Proof. Corollary 3.7 settles the non-det-extremal case. If 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 of Lemma 3.18. Lemma 3.15 colours and Corollary 3.7 colours 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 and , let be obtained by inserting one block on each edge of . Call the edges of marked. A signing of a simple bipartite graph with a perfect matching is Pfaffian if is the same for all perfect matchings of . 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 is central if 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 .
Lemma 3.20. Let be a loopless cubic multigraph whose truncation has a strong 6-edge-colouring. Inserting one on each of the three edges incident with a vertex preserves colourability while fixing every retained state except the state at , and every external colour away from those three edges.
Proof. Change the state at from to . On the block at port , prescribe boundary colours toward the old neighbour and toward , with common pair . Proposition 2.3 applies. The outer signature is the former signature at , while is disjoint from the new pair at the inner interface. All other interfaces are unchanged. If is bipartite, the new base is also bipartite.
Proposition 3.21. The base consisting of two vertices joined through three disjoint copies of is bipartite and has a truncation of strong chromatic index six.
Proof. At the two new vertices use and , ordering ports by the three blocks. Prescribe the following data on those blocks, listing their two boundary colours and common exposed pair:
Proposition 2.3 realises them. At either new vertex the exposed pairs are , 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 of minimum order to Theorem 1.1 has the form , where is simple, 3-connected, cubic and bipartite, , and every vertex is incident with at most two edges of . Moreover, is det-extremal and the signing of negative precisely on is Pfaffian.
Proof. Theorem 3.19 and Corollary 3.7 imply that 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 , minimality gives a colouring of each truncation. Gluing along the markers as in Lemma 2.2 would then colour , a contradiction. Hence every 2-edge cut isolates a single block .
Triple edges would give ; double-edge blocks are vertex-disjoint. If they cover , 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 with .
If has exactly two parallel edges , at least one is marked. The vertices 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 is simple unless . In the latter case zero marked edges give the excluded ; 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 had a 2-edge cut, both shores would have at least four vertices, since is simple, cubic and bipartite. The cut would lift to one of : for each marked cut edge, cut one outside edge of its block. Neither shore of the lifted cut would be a single . Thus 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 , so it is not . Lemma 3.20 would extend this colouring. The marked degree is therefore at most two. A perfect matching of uses either both or neither of the outside edges of each block. It therefore projects to a perfect matching of : for a marked edge in it uses both outside edges, and for a marked edge outside it chooses one of the two internal edges. Every has such a lift . 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 interchanges two matched images. Thus
Since is det-extremal, the signing negative precisely on 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 be a simple cubic bipartite graph with a Pfaffian signing negative precisely on . Each 4-cycle of contains either one or three edges of .
Proof. Every 4-cycle in is central. Indeed, deleting it preserves the equality of the partition sizes. If Hall’s condition failed for a set on one side of , degree counting would give : the two opposite-part vertices of have only two incidences outside . This contradicts . Extend a perfect matching of by either of the two matchings of . Switching between them multiplies the permutation sign by and the product of edge signs by . Their product must be unchanged, so the number of marks on is odd.
When 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 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 . 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 be the closures, with root edges numbered according to the original cut edges. For each , a perfect matching of using root edge ; one exists since is cubic and bipartite. Every perfect matching of using root edge combines with it to give a perfect matching of . The symmetric difference of two such matchings lies in , so extension preserves the ratio of their signed determinant terms. The Pfaffian signing of therefore makes all terms in this class have a common sign in , initially assigning positive signs to its root edges. Assigning sign to root edge makes every term positive, without changing any non-root sign. Apply the same argument to .
Lemma 3.25. Let be a simple 3-connected cubic bipartite Pfaffian graph without a 4-cycle. Then 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 is cyclically 4-edge-connected. Otherwise choose a smallest shore of a nontrivial 3-edge cut and let be its closure, with root . By Lemma 3.24, is simple, 3-connected, cubic, bipartite and Pfaffian. It is cyclically 4-edge-connected: a nontrivial 3-edge cut in would have a shore avoiding , strictly contained in , and lifting to a smaller such shore in . If were not Heawood, its two disjoint 4-cycles would include one avoiding , hence a 4-cycle of , 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 be obtained from the cycle by inserting on , and let instead have on . Give each one outside port. If the signatures prescribed by the exterior, in the order , are
where are disjoint two-element subsets of and are disjoint two-element subsets of , then the augmented truncation of each 4-pole has a strong 6-edge-colouring compatible with these signatures.
Proof. Order the ports at each as outside, forward, backward. In a state the outside port has signature . By Proposition 2.3, a block can join signatures whenever and a two-element subset exists; use as its common exposed pair.
For , Table 3 realises the following exposed-pair patterns in both 4-poles, with outside colours and normalisation :
Table 3.
We choose a pattern whose four pairs avoid , respectively. Put .
If , write and . Set if , and otherwise. Then , and . If , use with and . Otherwise write with and : for take ; otherwise take and . Write with . Pattern works: avoids , avoids , avoids , and avoids . If , interchange and simultaneously in this argument, obtaining or in the original order. The latter has its own realisation; no reflection of the 4-pole is assumed.
If , then partition . Set if , and otherwise. Now and . For , use with . Otherwise choose and , which exist since , and write and . Pattern works: avoid , and avoid .
For , both 4-poles realise
with outside colour and normalisation . Put and let , . The family is invariant under simultaneously swapping its first two and last two entries, by renaming as , and under swapping its last two entries, by renaming them as . These are symmetries of colour assignments, not of the pole. If , they allow us to assume with . Write , take any and put . The colours are distinct, and , avoid , respectively.
If and , write , , , . Taking gives pairs . In the two remaining cases normalise , , , 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 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.
| Pattern | Pole | |||||||
| — | — | |||||||
| — | — | |||||||
| — | — | |||||||
| — | — | |||||||
| — | — | |||||||
| — | — | |||||||
| — | — | |||||||
Table 3 (PDF p. 15). Realisations of the seven patterns, in port order outside, forward, backward. A listed pair is exposed at both ends of the block on ; 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 with root , or the core is itself the Heawood graph. Since is det-extremal, any Pfaffian signing of differs from the all-positive signing on a cut [7 Corollary 4.3]. Thus on the marked edges are exactly those joining different values of a binary vertex function. Its values at the three neighbours of determine which smaller pole suffices for the replacement.
Lemma 3.27. Let be the Heawood graph, and . Form a 3-pole by replacing each edge of with by one block . If is constant on , then is an exact vertex simulator. Otherwise let be the unique neighbour with the minority value. Then realises every ordered boundary-signature triple realised by a vertex with a single block on the arm corresponding to .
Proof. If the neighbours of have common value , extend by and put . No edge at is expanded in . The matching-lift calculation in Lemma 3.22 shows that every perfect matching of the expanded graph projects to a perfect matching of and has sign
Here , since matching edges inside cover vertices in pairs. Thus is det-extremal, as is. Deleting gives , so Theorem 3.9 applies.
For the mixed case write in the cyclic model of Section 3.3:
Translations and give vertex transitivity. The vertex stabiliser acts as 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 and, by complementing , assume , . For the tables below, order the port set at arms and those at by increasing index in of their -neighbours. Missing ports retain their positions, namely at .
Normalise the central state of the comparison pole, with the marked arm first, to . Its direct-arm signatures are , ; its other signature is , where
The automorphism , combined with the colour permutation , fixes the minority arm and interchanges the majority arms while preserving their signatures. Its orbits on the nine possibilities are
It suffices to realise the five representatives in Table 5. Assign to each vertex the state 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 of gives endpoint signatures satisfying
Table 4.
Table 5. The three states depending on the boundary signature.
Table 4 (PDF p. 16). States common to all five cases.
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 . The boundary rows give exactly . 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 as in Lemma 3.22. Suppose first that has a 4-cycle . By Lemma 3.23, is one or three. The graph is connected, since each component would require at least three of the four edges leaving . Label so its expanded pole is or . Delete that pole, retaining all blocks on edges leaving , and pair the free incidences as . This gives a connected loopless cubic bipartite multigraph : each new edge joins opposite partition sets. Moreover , 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 and
Thus and . Minimality gives a colouring of . 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 , a contradiction.
Assume now that has no 4-cycle and is not Heawood. Lemmas 3.25 and 3.24 give a Heawood closure , rooted at , with a Pfaffian signing agreeing with on its non-root edges. Write its negative edges as a cut, with binary vertex function , as in the construction above. Replace the expanded shore by a vertex if is constant on , 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 is connected, loopless, cubic and bipartite. The complementary closure of is simple cubic bipartite, so . Replacing the thirteen Heawood vertices and their internal blocks by at most three vertices gives . Minimality colours ; Lemma 3.27 then restores the shore with unchanged boundary signatures, a contradiction.
Finally let be the Heawood graph. Again is a non-empty cut: write and . Choose incident with , of marked degree . Replace the expanded by its single-block comparison pole. If , 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 , 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 , a final contradiction. The lower bound (1) gives equality.
Claw-free cubic multigraphs
Let be a connected bridgeless cubic claw-free multigraph different from the 3-bond . We prove Theorem 1.2 directly, whether or not has parallel edges. The block decomposition first identifies the chains of diamonds and parallel-edge blocks in . We then show which chains can be restored without changing the colours at their attachments. Only a single block 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 account for the vertices lying on no triangle.
Lemma 4.1. Suppose . The parallel-edge blocks , the induced diamonds and the triangles outside all diamonds partition . Each block and each diamond has two edges leaving it, and each triangle block has three.
Proof. A triple edge would give the excluded component . Thus each parallel pair forms a block , and these blocks are vertex-disjoint by cubicity. If both ends of a block had the same outside neighbour, the remaining edge at that neighbour would be a bridge. Hence no vertex of 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 ; 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 for the resulting multigraph. Its triangle vertices have degree three, and its other vertices have degree two.
Lemma 4.2. If has no triangle block, is a cycle, possibly of length two. Otherwise the edges of 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 , the skeleton of . Replacing the corresponding chains in by edges between their attachment vertices gives a reduced base .
Proof. is connected and bridgeless: a bridge between contracted blocks would lift to a bridge of . If every vertex has degree two, 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 , contrary to bridgelessness. Thus the paths have distinct endpoints and their suppression produces a loopless cubic multigraph .
Each retained triangle of now corresponds to a vertex of . 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 . This identifies the reduced graph with , even when two paths give parallel edges of . □
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.

Figure 3. Suppression of a diamond chain in the base graph. The two triangle blocks and their attachment vertices are retained, and the chain is replaced by an edge . 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 and exposed pairs at its two ends. The diamond must expose a pair disjoint from at the first join and one disjoint from at the second. We can arrange for these pairs to be and , respectively, which also permits iteration.
Lemma 4.3. Let be a diamond with tips and centres . Let , and let be disjoint 2-element subsets of . Equip with one dangling half-edge at each tip. Its augmented truncation admits a strong edge-colouring with colours in whose boundary signatures are
Proof. Identify with . Use the colouring in Table 6. The first ports at are the boundary ports.
Each row contains all six colours. The five internal interfaces of the 2-port piece are checked explicitly below:
| base edge | external colour | first exposed pair | second exposed pair |
Table 7.
The external colours agree and the exposed pairs are disjoint at every interface, so Lemma 2.1 applies. The boundary signatures are at and at .
Choose a permutation of taking to , to , and to , 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 be a loopless cubic multigraph, let be a strong edge-colouring of with colours in , and let . For each , choose a positive integer , and form by replacing with a chain of diamonds. Then admits a strong edge-colouring with colours in that agrees with on every retained canonical triangle and on every external edge corresponding to an edge of .
Proof. At the endpoints of a replaced edge, write the old signatures as . By Lemma 2.1 the pairs are disjoint and avoid . Orient the chain from to and use Lemma 4.3 on each diamond, with entry signature and exit signature . At every join, including the first and the last, the colour is and the exposed pairs are . 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.

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 and exit signature , so every join compares the disjoint pairs , regardless of the chain length. For there is one diamond; for the end blocks are joined directly.
A closed chain in the block decomposition may contain both diamonds and copies of . 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 and diamond 2-poles, other than the closure of one copy of , has a truncation of strong chromatic index six.
Proof. For the explicit colourings take . If there are no blocks , orient the cycle and use the diamond colouring of Table 6 on every block, with entry signature and exit signature . Every join is compatible, including the closing one. For one diamond, joining its tips gives .
If there are at least two copies of , suppress the intervening diamond chains. Proposition 2.4 colours the truncation of the resulting cycle of blocks , and Lemma 4.4 restores the suppressed chains with all retained states fixed.
It remains to treat one and at least one diamond. For one of each, take a diamond with tips and centres , parallel edges between , and joins . The following states give compatible interfaces:
| Vertex | Ordered ports | Local state |
Table 6. A strong 6-edge-colouring of the 2-port truncation of a diamond. The signatures at its two outside ports are and .
| vertex | port order | state |
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 , 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 stay fixed.
Corollary 4.6. Let be a loopless cubic multigraph with a strongly 6-edge-coloured truncation. Replacing an edge of by a non-empty chain of copies of and diamonds preserves this colourability, with all retained local states and all other external colours fixed, unless the chain consists of a single .
Proof. If the chain is not a single , closing it by an edge gives a base other than . Proposition 4.5 colours its truncation. The gluing described above now inserts the chain. A single 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 and , let be obtained from by inserting a block into the external edge corresponding to each . Thus . For the base above, will consist precisely of the edges of its skeleton that represent a single . In this construction itself need not be bridgeless.
In each triangle of contributes a piece 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 , and , with outside ports .
Figure 5. The 9-vertex piece , with ports , , shown as open circles. Dashed segments represent the three interblock edges.
We use the same palette throughout this construction. The following property of lets us adapt a boundary colour to a neighbouring block without changing the exposed pair.
Lemma 4.7. Fix two colours and a two-element set , with . Any assignment of colours from to the three outside ports of extends to a strong 6-edge-colouring of the augmented piece with exposed pair at every outside port.
Proof. Up to permuting colours and ports, take and prescribe with . Let be the other element of . 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:
Each outside port exposes . The three joins have colours , respectively. The pairs across them are and , 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 are distinct, the two ports of colour may expose and the port of colour may expose . In the same cyclic port order, the states
give this prescription for , with boundary colours . At the three joins the pairs are and . 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 : 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 has a proper 3-vertex-colouring, then .
Proof. Partition the palette into pairs , , . Fix representatives once and use as the three vertex colours of . Prescribe at every port of a triangle piece the exposed pair assigned to its vertex. For each edge of choose the boundary colours as in the table, up to permuting the pairs together with their fixed representatives.
| edge of | endpoint pairs | boundary colours | pair on |
| — | |||
Table 1 (PDF p. 21).
The first row covers every unmarked edge because the colouring of is proper. In the last row the choice of which endpoint receives is immaterial. All boundary colours at a piece assigned lie in , so Lemma 4.7 realises the three prescriptions simultaneously; the same holds for and . Unmarked interfaces are compatible by the first row. On each marked edge the common pair on 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 , every component of contains a vertex incident in with an edge of , since is connected. This vertex has degree at most two in . 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 , the underlying simple graph of is connected of maximum degree at most three. By Brooks’ theorem [3] it too has a proper 3-vertex-colouring, unless it is (paths and cycles also admit three colours). In the latter case cubicity forces itself. This leaves .
Proposition 4.9. Let . Then admits a strong 6-edge-colouring.
Proof. Label the vertices of by so that its four triangle blocks have vertex sets
and the six edges between these triangles are
For a vertex of , list its neighbours in increasing order as . Use the local states in Table 7 to colour , with the ports at each vertex in this order.
In every row, the two colour triples together contain exactly . The external colours agree at both endpoints of every edge of , so the colouring is well-defined. Each exposed pair is obtained by deleting from the opposite internal triple. All eighteen interfaces are listed below; each edge is specified by its two vertex labels.
| 01 | 02 | ||||
| 03 | 12 | ||||
| 16 | 29 | ||||
| 34 | 35 | ||||
| 45 | 47 | ||||
| 510 | 67 | ||||
| 68 | 78 | ||||
| 811 | 910 | ||||
| 911 | 1011 |
Table 2 (PDF p. 21).
Every displayed pair of sets is disjoint, so Lemma 2.1 gives the required strong colouring.
| Local state | ||
| 0 | ||
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 | ||
| 11 |
Table 7 (PDF p. 22). A complete local-state certificate for when .
Lemma 4.10. For every connected loopless cubic multigraph and every , the graph satisfies
Proof. The preceding argument gives a proper 3-vertex-colouring of in every case except and . 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 , 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 by Lemma 4.2, so Proposition 4.5 again applies.
If there is a triangle block, Lemma 4.2 gives the reduced base . Mark the edges of that represent a single . Lemma 4.10 colours , 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 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 , not necessarily connected, admit a partition into triangles, then . In particular, every loopless cubic multigraph satisfies
including when has bridges or is disconnected.
Proof. Contract the triangles of , 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 with . On every component of use Lemma 4.10 with and reuse the palette between components. Conversely, the canonical triangles give the required partition for every base of the form . When 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 .
Concluding remarks
The strong chromatic index of is six for connected cubic bipartite multigraphs and for connected bridgeless cubic claw-free multigraphs, with the sole exception of the 3-bond (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: for every loopless cubic multigraph , since the canonical triangles partition the vertices of .
Beyond the bipartite and claw-free classes, the multigraph form of Kardoš’s question remains open:
References
- [1]L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992), 231–252.DOI
- [2]J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, London, 2008.
- [3]R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.
- [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]P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math. 72 (1988), 81–92.
- [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]M. Funk, B. Jackson, D. Labbate and J. Sheehan, Det-extremal cubic bipartite graphs, J. Graph Theory 44 (2003), 50–64.DOI
- [8]P. Hall, On representatives of subsets, J. London Math. Soc. s1-10 (1935), 26–30.
- [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]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]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]F. Kardoš, Private communication clarifying the intended bridgeless formulation of Problem 4.1 of the 33rd Workshop on Cycles and Colourings.
- [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]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]W. McCuaig, Even dicycles, J. Graph Theory 35 (2000), 46–68.
- [16]S.-il. Oum, Perfect matchings in claw-free cubic graphs, Electron. J. Combin. 18 (2011), no. 1, Paper P62.DOI
- [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]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.
