Fabian Arevalo

Graph colouring · Cycles and Colourings 2025, Problem 4.1

A diamond-free claw-free cubic graph that needs seven colours

An 18-vertex counterexample to the question as posed, a proved local obstruction that generates infinitely many more, and the two readings of the question that survive it.
26 August 2026 · exhaustive computation, every instance carrying a checked certificate · code, censuses and the machine proof in the Matematica repository.

Start here — no maths required

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.

Show
G18, the smallest counterexample. Eighteen corners, twenty-seven edges, six triangles. Everything drawn here is computed in your browser from the single string Q??CA?_cAOA_DC@`PO@OOOW?`_?, which encodes the graph: the triangles are found by search, the quotient is read off by contracting them, and the colours in the 7-colouring view are the certified witness from the repository, checked live against the colouring rule as the figure draws. Structure shows the six triangles and the nine links between them. Colouring writes the colour index on each edge, so the witness can be spot-checked by eye; the readout reports the full check. Balloons highlights the two pieces that make six colours impossible. Bridge highlights the single edge whose removal disconnects the graph, which turns out to matter a great deal.

What this note adds

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.

  1. The question as posed is answered, and the answer is no. There is an 18-corner shape needing seven colours. A machine proof that six are impossible was checked by an independent verifier, and a valid seven-colouring is exhibited. It is the smallest such shape and the only one with 18 corners.
  2. There is a reason, and it is local. A small configuration, which I call a balloon, makes six colours impossible on its own, no matter what the rest of the shape looks like. The proof is ten lines and does not need a computer. It produces counterexamples at every size from 18 corners upward.
  3. But every counterexample has a weak point. This is the part that changes how the result should be read. A balloon always forces a bridge: a single edge holding the shape together, whose removal breaks it in two. So the failure lives entirely among shapes with a weak point. Among the 36,093 cases checked exhaustively, all 6,305 failures have one, and all 26,867 cases without one are colourable with six.
  4. The reading Kardoš probably intended survives everything tested. If the shape you truncate is an ordinary graph, with no repeated edges, six colours always sufficed: verified for all 556,471 such shapes with up to 20 corners, giving truncations with up to 60 corners. Each one carries a colouring that was re-checked against the definition.
  5. An exact law, so far without exceptions. Across all 36,093 truncated shapes with up to 16 corners in the quotient, seven colours are needed precisely when a balloon is present. Not one case falls on the wrong side. Half of that law is proved; the other half is a conjecture, checked on 317,246 further cases.

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.

AbstractSummary of results

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.

Section 1The class the question is about

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.

Lemma 0 · structure

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.

the crack
{ diamond-free claw-free cubic } = { K4 } ∪ { T(H) : H cubic loopless multigraph }
⊋   { T(G) : G cubic simple graph }
The counterexample lives in the difference. The right-hand family is verified 6-colourable for every G on at most 20 vertices (§6).

The dart model

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).

Section 2The balloon obstruction

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.

Theorem 3 · Balloon Lemma · proved

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.

Piece
The obstruction, enumerated live. This is a measurement, not a schematic: your browser runs the full search over every assignment of the dart model to the piece and reports how many survive. Press Apply next constraint to impose the conditions in the order of the proof. For the balloon the count goes 51,840 vertex-legal assignments, then 2,880 after the doubled-edge condition of Step 2, then 0 after the shared-neighbour condition of Step 3, which is exactly zero of the 60 conceivable boundary states. For the dumbbell, the same computation on the same code path ends at 180 realizable boundary state pairs, matching the closed form 15 × 12 counted by hand in Lemma 4. The single structural difference between the two pieces is whether the two stems land on the same vertex.
Lemma 4 · dumbbell transfer · proved

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.

Section 3The counterexample

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.

Theorem 5

(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.

ClaimLabelWhat backs it
χ′s(G18) ≥ 7Proved 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) ≤ 7Certified An explicit 7-colouring, re-verified from the induced-matching definition. It is the colouring the figure above draws.
G18 is in the classCertified 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 18Certified 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 ≤ 8Certified 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.

Section 4Every counterexample has a bridge

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.

Proposition 6 · proved

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.

Corollary · conditional

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.

Section 5The census

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.

Population
Scale
The whole census, and the control that empties it. Every bar is a measurement: the counts come from the committed census files, one record per quotient, each record carrying its own checked certificate. Filled area is χ′s = 7, outlined area is χ′s = 6. Switching to Bridgeless only restricts to quotients with no bridge and the filled area vanishes completely, at every order. That is Proposition 6 as a picture: no bridge, no balloon, no counterexample. The one case not shown is the order-2 quotient, the triple edge, whose truncation is the prism with χ′s = 9; it is bridgeless and it is the classical exception to everything in this area, including Lin and Lin's bound.
Order of HQuotientsχ′s = 6χ′s = 7BridgelessBridgeless, not 6-colourable
2100 (prism: 9)11 (the prism, 9)
422020
665150
820164160
10917219660
125094071023650
143,6082,9266822,6020
1631,85626,3595,49723,8110
Total36,09329,7876,30526,8681 (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:

Conjecture C · characterization

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.

Section 6What survives

The simple-quotient reading

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.

The bridgeless reading

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.

Wires, and the class with diamonds

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:

PieceRelation between its two boundary statesCount
Diamondcolour preserved, pairs disjoint180
Dumbbellcolour changed, pair preserved180
Balloonnone, no valid internal state0

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.

Section 7Open questions, and what this does not settle

  1. Conjecture C's open half: balloon-free and not the triple edge implies χ′s(T(H)) = 6. The dumbbell transfer relation and a GF(2) sufficient condition are the tools in hand. The GF(2) construction, fixing a proper 3-edge-colouring of H and colouring by (colour, sign) pairs, reduces to three parity systems that are not always solvable, so it gives a sufficient condition and not a proof. That failure is recorded rather than hidden: it was the session's main attempt at the converse.
  2. The bridgeless case as a standalone question. Proposition 6 makes it the natural sharpening of Problem 4.1, and it is untouched by the counterexample. It is implied by Conjecture C but might well be easier.
  3. Kardoš's intended question in full. §6 verifies it to order 20. Is there a proof for 3-edge-colourable H, for bipartite H, or in general?
  4. A counting sequence. The number of χ′s = 7 quotients by order is 1, 4, 19, 102, 682, 5497, equivalently the number of balloon-containing cubic multigraphs if Conjecture C holds. It matched nothing found by search and is worth checking against OEIS properly.
  5. Novelty is a search claim, not a proof. No published resolution of Problem 4.1 and no diamond-free tight example were found, on the research session's search and again on a full-access re-check while writing this page. That is a literature search and nothing stronger. Han and Cui's paper and Lv, Li and Zhang's paper were not read; they are cited through Kardoš's own text, which was read in the original.