Graph colouring · Cycles and Colourings 2025, Problem 4.1
Take a shape where exactly three edges meet at every corner: a cube, or the frame of a football. Now slice off every corner, so each corner becomes a small triangle. That operation is called truncation, and a truncated cube or a truncated icosahedron is what you get.
Now colour the edges. The rule is stricter than usual: two edges must differ in colour not only when they touch, but also when they are one edge apart. Think of each edge as a radio transmitter that jams its neighbours and its neighbours' neighbours, so nothing within one step of anything else may share a frequency. How many colours do you need?
Six is clearly the minimum, and you can see why on any one of those little triangles. Its three edges, plus the three edges leaving its corners, make six edges that are all within one step of each other, so all six need different colours. The question is whether six is also enough. In November 2025, at a workshop in Slovakia, František Kardoš wrote this down as an open problem: for every such truncated shape, do six colours suffice?
The answer is no. There is a shape with 18 corners for which six colours are provably impossible and seven are needed. It is drawn below. It is the smallest one, and it is the only one of its size.
What was known: Lv, Li and Zhang showed eight colours always suffice for this class of shapes, and Lin and Lin improved that to seven, with infinitely many examples that genuinely need all seven. But every one of their examples contains a diamond, a particular four-corner pattern that truncated shapes never contain. So the truncated case was left open, and Han and Cui had settled only one family of it, the truncated prisms.
The technical version follows. Section 2 has the proof of the obstruction, with a figure that enumerates it live; section 4 is the bridge caveat and is the part a specialist should read first; section 5 has the census with a control that makes every counterexample disappear.
Kardoš asked (Problem 4.1, §4 of the open problems of the 33rd Workshop on Cycles and Colourings, arXiv:2511.02892v1, 4 November 2025): is every diamond-free claw-free cubic graph strongly 6-edge-colorable, in other words is χ′s(T(G)) = 6 for every cubic graph G? The two phrasings come apart, and the first is false.
Diamond-free claw-free cubic graphs are exactly K4 together with the truncations T(H) of connected cubic loopless multigraphs H. A doubled edge of H whose two endpoints share their third neighbour, a balloon, is a complete local obstruction: if H contains one, T(H) has no strong 6-edge-colouring (Theorem 3, Proved). This yields diamond-free claw-free cubic graphs with strong chromatic index 7 at every admissible order 18 + 6k; the smallest, G18, has 18 vertices and is unique at that order (Certified).
Every such counterexample is necessarily bridged: a balloon's stem is always a bridge (Proposition 6, Proved). Since the structure theorem the question rests on is Oum's, stated for 2-edge-connected graphs, the refutation does not touch the bridgeless reading, and the census supports that reading instead: all 26,867 bridgeless quotients of order at most 16, other than the triple edge, give strongly 6-edge-colourable truncations.
A double-verified census of all 36,093 truncations of cubic multigraphs of order at most 16 finds χ′s(T(H)) = 6 exactly when H is balloon-free and is not the triple edge, whose truncation is the prism with χ′s = 9. That characterization is proved in one direction and conjectural in the other, with the open direction verified for a further 317,246 balloon-free quotients of order 18. Finally, the intended reading survives: every truncation of a simple connected cubic graph on at most 20 vertices, 556,471 graphs with truncations on up to 60 vertices, is strongly 6-edge-colourable.
A strong edge colouring colours the edges of a graph so that every colour class is an induced matching: two edges of the same colour neither share a vertex nor are joined by an edge. Equivalently it is a proper vertex colouring of the square of the line graph. The least number of colours is the strong chromatic index χ′s(G).
The truncation T(H) of a connected cubic loopless multigraph H replaces each vertex u by a triangle on vertices ue indexed by the edge instances e at u, and joins ue to ve for each instance e = uv. It is a connected simple cubic graph on 3·n(H) vertices. A diamond is K4 minus an edge and a claw is K1,3, both as induced subgraphs.
The connected, cubic, claw-free, diamond-free simple graphs are exactly K4 and the truncations T(H) of connected cubic loopless multigraphs H, and H is determined by T(H) up to isomorphism.
The proof is a triangle count: claw-freeness forces every vertex to have at least one edge among its neighbours, having two such edges creates a diamond, and having three isolates a K4 component, so in the remaining case every vertex lies in exactly one triangle, the triangles partition the vertices, and contracting them gives H.
This is almost the "well-known fact" Kardoš quotes, and the gap between them is where the whole note lives. For 2-edge-connected graphs the statement is the diamond-free case of Oum's Proposition 1, and Oum's proof of that case is the same triangle contraction. Oum's H is explicitly a multigraph. Kardoš's second phrasing writes T(G) for "a cubic graph G", and if G is read as a simple graph the two phrasings describe different families. Everything below turns on that.
Fix H with n(H) ≥ 2. A dart is an incidence (u, e). Strong 6-edge-colourings of T(H) correspond bijectively to pairs (c, t), where c colours the edge instances of H and t colours the darts, subject to two conditions: at every vertex u the six values c(e), c(f), c(g), tu(e), tu(f), tu(g) are pairwise distinct, and for every instance e = uv, tu(x) ≠ tv(y) for all darts x ≠ e at u and y ≠ e at v. Here c(e) is the colour of e's link edge and tu(e) is the colour of the triangle edge of u opposite ue.
Two consequences are used constantly. Around every triangle the six incident edges pairwise conflict, so χ′s(T(H)) ≥ 6 always, and deciding 6-colourability decides χ′s = 6 against ≥ 7. And writing P(u) for the link palette at u and P̄(u) for its complement, tu is a bijection from u's darts onto P̄(u).
Two configurations in a quotient H. A dumbbell is a doubled edge x‖y whose endpoints' third edges, the stems, run to two distinct vertices. A balloon is a doubled edge u‖v whose endpoints' third edges uw and vw meet at a common vertex w. A balloon is what a loop at w becomes when the loop is expanded into a digon.
If H contains a balloon, then T(H) has no strong 6-edge-colouring, so χ′s(T(H)) ≥ 7.
Proof. Suppose (c, t) exists. Let the balloon be u‖v with instances e1, e2, let f = uw and g = vw, and let s be w's third edge. Put a = c(e1), b = c(e2), x = c(f), y = c(g).
Step 1: x ≠ y. If x = y then P̄(u) = P̄(v) =: P, a 3-set. The edge condition for e1 asks the two 2-sets P ∖ {tu(e1)} and P ∖ {tv(e1)} to be disjoint, which is impossible inside a 3-set.
Step 2: the doubled edge freezes everything. Write {0,…,5} = {a,b,x,y} ⊔ {p,q}. Then P̄(u) = {y,p,q} and P̄(v) = {x,p,q}. The edge condition for e1 makes P̄(u) ∖ {tu(e1)} and P̄(v) ∖ {tv(e1)} disjoint; since p and q lie in both complements each must be removed on at least one side, forcing {tu(e1), tv(e1)} = {p,q}, and likewise for e2. As tu is injective this gives {tu(e1), tu(e2)} = {p,q} and therefore tu(f) = y, and symmetrically tv(g) = x.
Step 3: the shared neighbour has nowhere to go. The edge condition for f = uw gives {p,q} ∩ {tw(g), tw(s)} = ∅, and the one for g = vw gives {p,q} ∩ {tw(f), tw(s)} = ∅. So no tw-value is p or q, that is {p,q} ⊆ P(w) = {x, y, c(s)}. But p and q are not x or y by construction, so both would have to equal c(s). Contradiction. ∎
The proof never touches the far side of the stem, so the balloon piece is infeasible in isolation, which is stronger than needed. That is what the figure below enumerates, and it is also what makes the contrast with the dumbbell sharp: change "shared neighbour" to "two different neighbours" and the same piece goes from impossible to richly realizable.
Across a dumbbell the two stem colours differ and both boundary pair-sets coincide: the transfer relation is exactly {((c1,S),(c2,S)) : |S| = 2, c1 ≠ c2, {c1,c2} ∩ S = ∅}, which is 180 labelled pairs. Every pair of that shape is realizable.
Let H6 be the 6-vertex quotient consisting of two balloons whose stems are joined by a single bridge, and let G18 = T(H6), on 18 vertices, graph6 string Q??CA?_cAOA_DC@`PO@OOOW?`_?. This is the graph in the figure at the top of the page.
(1) G18 is a connected claw-free diamond-free cubic simple graph with χ′s = 7, so the answer to Problem 4.1 in its class-level phrasing is no, and among claw-free cubic graphs the tight value 7 is attained without diamonds.
(2) G18 is the unique smallest such graph: every diamond-free claw-free cubic graph on fewer than 18 vertices other than the prism, which has χ′s = 9, is strongly 6-edge-colourable, and G18 is the only exception on exactly 18.
(3) For every k ≥ 0 the chain quotient Ck, two balloons joined through k dumbbells, gives such a graph on 18 + 6k vertices with χ′s ≥ 7. Graphs in this class exist only on order 4 and on multiples of 6, so every admissible order from 18 upward carries a counterexample.
Membership in the class is Lemma 0, or the definition-level check in the verifier. The lower bound χ′s ≥ 7 is Theorem 3, needing no computation. The rest is certified rather than proved, and here is exactly what the certificates are.
| Claim | Label | What backs it |
|---|---|---|
| χ′s(G18) ≥ 7 | Proved | Theorem 3. Independently, UNSAT of the definition-level CNF at six colours with a 4,200-line DRUP proof, re-checked by a from-the-definition RUP checker (re-run during this write-up: s VERIFIED, 759 clauses, 4,200 proof lines). |
| χ′s(G18) ≤ 7 | Certified | An explicit 7-colouring, re-verified from the induced-matching definition. It is the colouring the figure above draws. |
| G18 is in the class | Certified | Cubic, connected, zero induced claws and zero induced diamonds among all 3,060 four-subsets, six vertex-disjoint triangles. Re-checked independently for this page. |
| Uniqueness at order 18 | Certified | Two independent enumeration paths agree: all 41,301 cubic graphs on 18 vertices filtered by the definition, and quotient generation followed by truncation. Both find exactly six graphs of the class on 18 vertices and the same single exception, with equal canonical forms. |
| χ′s(T(Ck)) = 7 for k ≤ 8 | Certified | Per-instance UNSAT at six plus a verified 7-colouring. For k > 8 the lower bound is Theorem 3 and the matching upper bound is Lin and Lin's theorem, cited not re-proved. |
Two independent engines decide every instance in this note and share no code: a complete backtracking search over the conflict graph written in C, and a definition-level CNF handed to a SAT solver in Python. A third implementation re-checks every witness from the definition, and rejects deliberately corrupted witnesses in a negative control. The definitional anchors C5 = 5, C6 = 3, C7 = 4, K3,3 = 9, Petersen = 5 and prism = 9 are all reproduced.
This section was not part of the research session. It came out of re-deriving the numbers before publishing, and it is the first thing a referee would ask about, so it belongs near the front rather than in a footnote.
If a connected cubic loopless multigraph H contains a balloon u‖v with common third neighbour w and stem s at w, then s is a bridge of H, and the link edge of s is a bridge of T(H). Consequently every graph the Balloon Lemma rules out is a bridged diamond-free claw-free cubic graph.
Proof. The vertices u and v already have degree 3 inside {u,v,w}, two parallel instances plus one edge to w, so no further edge meets them, and s cannot be a loop at w since H is loopless. Hence s is the only edge of H leaving {u,v,w}, so it is a bridge and n(H) ≥ 4. Replacing vertices by triangles neither creates nor destroys bridges among link edges, since triangle edges lie on triangles. ∎
G18 has exactly one bridge, so it is not 2-edge-connected. You can see it in the top figure under Bridge: it is the single link joining the two balloon halves, and it is the shared stem of both of them.
Why this matters. Oum's Proposition 1, the actual source of the structure fact the question rests on, is stated for 2-edge-connected claw-free cubic graphs, and a good deal of the cubic-graph literature carries a bridgeless hypothesis by default. Problem 4.1 as written has no connectivity hypothesis, so G18 refutes it as posed. But by Proposition 6 the refutation is confined to the bridged part of the class, and the census in the next section says the bridgeless part looks true. The honest one-line summary is: the class-level phrasing is false for bridged graphs, and both the bridgeless reading and the simple-quotient reading survive everything that was tested.
If Conjecture C below holds, then every 2-edge-connected diamond-free claw-free cubic graph other than the prism is strongly 6-edge-colourable, since a bridgeless quotient is balloon-free by Proposition 6. In other words the bridgeless reading of Problem 4.1 would be true.
All connected cubic loopless multigraphs were generated with nauty's geng and multig, with the counts cross-checked against OEIS A002851 and A000421 at every order used. Every 6-colourable instance ships a witness re-checked from the definition by a third implementation, which also re-derives the graph from the raw quotient line and locates a conflict 6-clique, certifying χ′s = 6 exactly. Every negative verdict is confirmed UNSAT by the second engine, and every one gets a verified 7-colouring, so χ′s = 7 is certified per instance without leaning on the literature bound.
| Order of H | Quotients | χ′s = 6 | χ′s = 7 | Bridgeless | Bridgeless, not 6-colourable |
|---|---|---|---|---|---|
| 2 | 1 | 0 | 0 (prism: 9) | 1 | 1 (the prism, 9) |
| 4 | 2 | 2 | 0 | 2 | 0 |
| 6 | 6 | 5 | 1 | 5 | 0 |
| 8 | 20 | 16 | 4 | 16 | 0 |
| 10 | 91 | 72 | 19 | 66 | 0 |
| 12 | 509 | 407 | 102 | 365 | 0 |
| 14 | 3,608 | 2,926 | 682 | 2,602 | 0 |
| 16 | 31,856 | 26,359 | 5,497 | 23,811 | 0 |
| Total | 36,093 | 29,787 | 6,305 | 26,868 | 1 (the prism, 9) |
Every χ′s = 7 instance contains a balloon, and every balloon instance has χ′s = 7. The only balloon-free failure in the whole table is the triple edge. That is an exact empirical law with zero exceptions in either direction across 36,093 cases, and it prompts:
For a connected cubic loopless multigraph H other than the triple edge, χ′s(T(H)) = 6 if and only if H contains no balloon, and otherwise χ′s(T(H)) = 7.
The direction "balloon ⇒ 7" is Theorem 3 together with Lin and Lin's upper bound. The open direction is "balloon-free ⇒ 6".
The open direction was pushed one order further under a lighter protocol. The 340,416 quotients of order 18 split as 287,459 balloon-free and 52,957 balloon. Every balloon-free one has a strongly 6-edge-colourable truncation: 286,805 decided by the backtracking engine with witnesses re-verified from the definition, and the 654 instances it capped decided by the SAT engine with witnesses checked in-engine. On the balloon side χ′s ≥ 7 is Theorem 3 and needs no computation, and a 500-instance random sample was independently confirmed UNSAT at six colours, 500 out of 500. Unlike the smaller orders, no per-instance 7-colourings were computed there. So the open half of Conjecture C stands verified for all 317,246 balloon-free quotients of order at most 18, the triple edge aside.
For every connected simple cubic graph G on n ≤ 20 vertices, that is 1 + 2 + 5 + 19 + 85 + 509 + 4,060 + 41,301 + 510,489 = 556,471 graphs, the truncation T(G) on up to 60 vertices is strongly 6-edge-colourable, with a definition-checked witness per instance. The 570 instances the backtracking engine capped were decided SAT by the second engine, 539 of them at order 20 alone. This extends Han and Cui's truncated-prism family to all simple quotients of order at most 20 and is, as far as a literature search shows, the first systematic verification of this reading of the problem.
One honest caveat on scale. The full 205 MB record file for order 20 is not committed; what is committed is the engine counts, the in-session verification record of all 509,950 witnesses, the 539 SAT-resolved caps, and a verified 2,000-record sample, together with the one-line command that regenerates the whole run in about 35 minutes on four cores.
Covered in §4 and visible in the figure above: all 26,867 bridgeless quotients of order at most 16 other than the triple edge give 6-colourable truncations, and by Proposition 6 no balloon-based counterexample can ever be bridgeless.
The interface calculus extends past truncations. In any cubic graph two edges conflict only within distance one, so across a bridge the two sides interact only through a colour and a pair of colours, with the junction rule "pairs disjoint". Three two-terminal pieces then act as wires with machine-enumerated transfer relations, and they form a trichotomy:
| Piece | Relation between its two boundary states | Count |
|---|---|---|
| Diamond | colour preserved, pairs disjoint | 180 |
| Dumbbell | colour changed, pair preserved | 180 |
| Balloon | none, no valid internal state | 0 |
Composing the diamond's relation with the junction rule on both sides gives exactly {(c,Sa) ~ (c,Sb) : Sa ≠ Sb}, strictly weaker than the bare edge's rule Sa ∩ Sb = ∅. So inserting a diamond into a bridge never destroys strong 6-colourability, though it is not a universal joint: equal pairs stay forbidden. This one is worth recording because the first hand derivation got it wrong, claiming the composed relation was vacuous; the verification script refuted that, since when the two outer pairs are equal the diamond's internal pairs have one colour left where two are needed.
Finally, a census of the whole claw-free class with diamonds allowed, orders 4 to 20. Such graphs are rare: 1, 1, 1, 1, 3, 3, 5, 11, 15 of them by order, of which 0, –, 0, 1, 0, 3, 1, 5, 5 have χ′s = 7, the prism being the entry marked "–" with χ′s = 9. The 10-vertex instance, a diamond plus two triangles, is by this census the smallest claw-free cubic graph with χ′s = 7. Whether it appears among Lin and Lin's tight examples was not checked; their list was not read.