Highly connected regular graphs with circular chromatic index \Delta + 2/3 for every \Delta \equiv 0 \pmod 4, \Delta \ge 8

What Lean checks

Lean proves the actual 4g-regular and 4g-connected graph with real circular index 4g+2/3 for every g ≥ 2, and the complete degree/connectivity/index statements for C25, C31 and C33. The real-colouring lower bound and atom/subgroup connectivity arguments are proved internally. Strict sources, an all-owned audit of 601 declarations/500 theorem declarations and 171 required endpoints, and exact stock-kernel replay passed. Local receipt. The nonregular Section 7 examples, structural/insertion lemmas, SAT exclusions, combined repository gate, and hosted validation remain separate.

Status: written proof with one independent model referee pass (written 2026-11-21). Theorems 1 and 2 and the regular C31/C33 examples of Section 7.2 now have complete Lean proofs, including degree, vertex connectivity, and the real circular chromatic index. Their 19-module closure passed strict source checks, an all-owned axiom audit, and stock-kernel replay; see the landing page and receipt. The nonregular examples, additional structural/insertion lemmas, and SAT exclusions remain outside that formalized scope. The Python checks remain verify.py and verify_part2.py; referee report and scripts are in review/.

0. Context

Mazák and Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822v1 (submitted 9 March 2026), Section 8, contains the following (quoted from the arXiv HTML version through a fetch tool; see Sources):

  • "It would also be interesting to know which denominators are possible in the upper half of the interval [Δ,Δ+1][\Delta, \Delta+1]."
  • Problem 7. "Does there for every integer q > 2 exist an integer p and a (multi)graph G with χ′c(G)=p/q∈(Δ(G)+1/2,Δ(G)+1)\chi'_c(G) = p/q \in (\Delta(G) + 1/2, \Delta(G) + 1)?"
  • "Currently, for any Δ≥8\Delta \geq 8, we don't even know if there is a single graph with maximum degree Δ\Delta and χ′c∈(Δ(G)+1/2,Δ(G)+1)\chi'_c \in (\Delta(G) + 1/2, \Delta(G) + 1)."
  • Problem 6. "For which d does there exist a d-connected d-regular graph with circular chromatic index at least d + 1/2?" It is preceded by: 3-connected cubic graphs with χ′c=3+1/2\chi'_c = 3 + 1/2 have long been known (Lukoťka–Mazák), and "Theorem 9 proves the existence of a 4-connected 4-regular graph G with χ′c(G)=4+1/2\chi'_c(G) = 4 + 1/2 (an infinite family of them, actually)" — namely the circulants C2n+1(1,2)C_{2n+1}(1,2), n≥6n \ge 6 (their Theorem 9: "There exist infinitely many 4-connected 4-regular graphs G with χ′c(G)=9/2\chi'_c(G) = 9/2").

The values in the open upper half that the paper lists have Δ≤6\Delta \le 6 (e.g. 11/311/3 Petersen, 14/314/3, 19/419/4, 23/523/5, 17/317/3, 23/423/4, 20/320/3, 27/427/4).

1. Statement

Notation. For an odd nn and S⊆{1,…,(n−1)/2}S \subseteq \{1, \dots, (n-1)/2\}, the circulant Cn(S)C_n(S) is the Cayley graph of ℤn\mathbb Z_n with connection set ±S\pm S: vertex set ℤn\mathbb Z_n, x∼yx \sim y iff x−y∈±Sx - y \in \pm S. The length of an edge {x,y}\{x,y\} is the unique s∈{1,…,(n−1)/2}s \in \{1,\dots,(n-1)/2\} with x−y≡±sx - y \equiv \pm s. α′(G)\alpha'(G) is the matching number.

Circular edge-colourings. For real r≥1r \ge 1, a circular rr-edge-colouring is a map φ:E(G)→[0,r)\varphi: E(G) \to [0, r) such that edges sharing a vertex get colours at circular distance dr(x,y)=min{|x−y|,r−|x−y|}≥1d_r(x,y) = \min\{|x-y|, r-|x-y|\} \ge 1; χ′c(G)\chi'_c(G) is the infimum (in fact minimum) of such rr (this is the definition used by Mazák–Zrubák). For integers p≥q≥1p \ge q \ge 1, a (p,q)(p,q)-edge-colouring is a map c:E(G)→ℤpc: E(G) \to \mathbb Z_p such that edges sharing a vertex get colours at circular distance ≥q\ge q in ℤp\mathbb Z_p. The colour classes are Ec=c−1(c)E_c = c^{-1}(c).

Theorem 1. Let g≥2g \ge 2, n=6g+1n = 6g+1 and

Gg=C6g+1(1,2,…,2g−2,2g+1,3g).G_g = C_{6g+1}(1, 2, \dots, 2g-2,\ 2g+1,\ 3g).

Then GgG_g is a simple 4g4g-regular, 4g4g-connected graph and

χ′c(Gg)=2n3=12g+23=4g+23=Δ(Gg)+23.\chi'_c(G_g) = \frac{2n}{3} = \frac{12g+2}{3} = 4g + \frac23 = \Delta(G_g) + \frac23 .

Theorem 2. The circulant H=C25(1,2,3,7,8,9,10,11,12)H = C_{25}(1,2,3,7,8,9,10,11,12) is a simple 18-regular, 18-connected graph with χ′c(H)=75/4=18+3/4\chi'_c(H) = 75/4 = 18 + 3/4.

Smallest cases of Theorem 1: G2=C13(1,2,5,6)G_2 = C_{13}(1,2,5,6) (Δ=8\Delta = 8, χ′c=26/3\chi'_c = 26/3), G3=C19(1,2,3,4,7,9)G_3 = C_{19}(1,2,3,4,7,9) (Δ=12\Delta = 12, χ′c=38/3\chi'_c = 38/3), G4=C25(1,…,6,9,12)G_4 = C_{25}(1,\dots,6,9,12) (Δ=16\Delta=16, χ′c=50/3\chi'_c = 50/3).

2. Proof

2.1 Two general lemmas on χ′c\chi'_c

Lemma 1 (lower bound). If GG has at least one edge, then χ′c(G)≥|E(G)|/α′(G)\chi'_c(G) \ge |E(G)|/\alpha'(G).

Proof. (This is the classical bound χ′c≥χ′f≥|E|/α′\chi'_c \ge \chi'_f \ge |E|/\alpha', cf. Zhu's survey and Hackmann–Kemnitz, the reference [11] of Mazák–Zrubák; here is a direct argument.) Let φ\varphi be a circular rr-edge-colouring (r≥1r \ge 1 by definition). For x∈[0,r)x \in [0,r) let Ix={x+tmodr:0≤t<1}I_x = \{x + t \bmod r : 0 \le t \lt 1\}, a half-open circular arc of length 1 (the whole circle if r=1r = 1). Two colours in IxI_x are at circular distance <1\lt 1, so Mx={e:φ(e)∈Ix}M_x = \{e : \varphi(e) \in I_x\} is a matching and |Mx|≤α′|M_x| \le \alpha'. Each colour lies in IxI_x for a set of xx of measure exactly 1, so

∫0r|Mx|dx=∑e∈E1=|E|⇒|E|≤rα′.\int_0^r |M_x|\,dx = \sum_{e \in E} 1 = |E| \quad\Longrightarrow\quad |E| \le r\,\alpha' .

Hence r≥|E|/α′r \ge |E|/\alpha' for every admissible rr, and the same holds for the infimum. ▫\square

Lemma 2 (upper bound and window form). (a) If GG has a (p,q)(p,q)-edge-colouring then χ′c(G)≤p/q\chi'_c(G) \le p/q. (b) A map c:E→ℤpc: E \to \mathbb Z_p is a (p,q)(p,q)-edge-colouring iff for every c0∈ℤpc_0 \in \mathbb Z_p the window Ec0∪Ec0+1∪…∪Ec0+q−1E_{c_0} \cup E_{c_0+1} \cup \dots \cup E_{c_0+q-1} is a matching.

Proof. (a) φ(e)=c(e)/q∈[0,p/q)\varphi(e) = c(e)/q \in [0, p/q) satisfies dp/q(φ(e),φ(f))=dℤp(c(e),c(f))/q≥1d_{p/q}(\varphi(e),\varphi(f)) = d_{\mathbb Z_p}(c(e),c(f))/q \ge 1 for adjacent e,fe,f. (b) Two adjacent edges with colours at circular distance t≤q−1t \le q-1 lie in a common window (the window starting at the "earlier" of the two colours along the shorter arc), and conversely two edges in a common window have colours at circular distance ≤q−1\le q-1. ▫\square

2.2 The graph

Let Sg={1,…,2g−2}∪{2g+1,3g}S_g = \{1,\dots,2g-2\} \cup \{2g+1, 3g\}. For g≥2g \ge 2 these 2g2g numbers are distinct (2g−2<2g+1<3g2g-2 \lt 2g+1 \lt 3g) and lie in [1,3g]=[1,(n−1)/2][1, 3g] = [1, (n-1)/2]; as nn is odd, s≢−ss \not\equiv -s, so ±Sg\pm S_g has 4g4g distinct non-zero elements and GgG_g is a simple 4g4g-regular graph with

|E(Gg)|=n⋅4g2=2gn.|E(G_g)| = \frac{n \cdot 4g}{2} = 2gn .

It is connected (1∈Sg1 \in S_g) and not complete (4g<6g=n−14g \lt 6g = n-1).

Every edge of GgG_g is {x,x+s}\{x, x+s\} for a unique length s∈Sgs \in S_g, and for fixed ss the nn translates {x+i,x+s+i}\{x+i, x+s+i\}, i∈ℤni \in \mathbb Z_n, are pairwise distinct: {x+i,x+s+i}={x+j,x+s+j}\{x+i,x+s+i\} = \{x+j, x+s+j\} with i≠ji \ne j would force x+i=x+s+jx+i = x+s+j and x+s+i=x+jx+s+i = x+j, hence 2s≡02s \equiv 0, impossible for odd nn. So the edges of length ss are exactly the nn translates of any one of them.

2.3 Upper bound: an explicit (2n,3)(2n, 3)-edge-colouring

Define two sets of gg edges ("base classes"):

M0={{0,4g}}∪{{2g+1+i,4g−i}:1≤i≤g−1},M1={{1,3g+1}}∪{{2g+1+i,4g+1−i}:1≤i≤g−1}.M_0 = \{\{0, 4g\}\} \cup \{\{2g+1+i,\ 4g-i\} : 1 \le i \le g-1\},\qquad M_1 = \{\{1, 3g+1\}\} \cup \{\{2g+1+i,\ 4g+1-i\} : 1 \le i \le g-1\}.

Vertex sets. {2g+1+i:1≤i≤g−1}=[2g+2,3g]\{2g+1+i : 1 \le i \le g-1\} = [2g+2, 3g], {4g−i}=[3g+1,4g−1]\{4g-i\} = [3g+1, 4g-1], {4g+1−i}=[3g+2,4g]\{4g+1-i\} = [3g+2, 4g]. Hence the vertex sets of M0M_0, M1M_1 are

V0={0}∪[2g+2,4g],V1={1}∪[2g+2,4g]V_0 = \{0\} \cup [2g+2,\ 4g], \qquad V_1 = \{1\} \cup [2g+2,\ 4g]

(intervals of integers, all inside [0,n−1][0, n-1]). Each has 2g2g elements and MεM_\varepsilon has gg edges, so M0M_0, M1M_1 are matchings.

Lengths. In M0M_0: {0,4g}\{0,4g\} has length n−4g=2g+1n - 4g = 2g+1; {2g+1+i,4g−i}\{2g+1+i, 4g-i\} has difference 2g−1−2i2g-1-2i, i.e. lengths 2g−3,2g−5,…,12g-3, 2g-5, \dots, 1 (all odd numbers in [1,2g−3][1, 2g-3]). In M1M_1: {1,3g+1}\{1, 3g+1\} has length 3g3g; {2g+1+i,4g+1−i}\{2g+1+i, 4g+1-i\} has difference 2g−2i2g-2i, i.e. lengths 2g−2,…,22g-2, \dots, 2 (all even numbers in [2,2g−2][2,2g-2]). So the 2g2g base edges have pairwise distinct lengths and their lengths are exactly SgS_g.

Classes. Index classes by a∈ℤ2na \in \mathbb Z_{2n}, writing a=2i+εa = 2i + \varepsilon with ε∈{0,1}\varepsilon \in \{0,1\}, i∈ℤni \in \mathbb Z_n (this is a bijection ℤ2n→{0,1}×ℤn\mathbb Z_{2n} \to \{0,1\} \times \mathbb Z_n, and a+2k↦(ε,i+k)a + 2k \mapsto (\varepsilon, i+k)):

class(2i+ε)=Mε+i.\mathrm{class}(2i+\varepsilon) = M_\varepsilon + i .

By 2.2, for each s∈Sgs \in S_g the nn classes Mε+iM_\varepsilon + i (ε\varepsilon the parity class containing the base edge of length ss) contain the nn distinct edges of length ss; thus the 2n2n classes partition E(Gg)E(G_g), each edge lying in exactly one class (2n⋅g=|E|2n \cdot g = |E| confirms the count). Each class is a matching (a translate of MεM_\varepsilon).

Colours. Since 3∤2n3 \nmid 2n (n=6g+1n = 6g+1), a↦3aa \mapsto 3a is a bijection of ℤ2n\mathbb Z_{2n}; colour every edge of class(a)\mathrm{class}(a) with c=3amod2nc = 3a \bmod 2n. As 3(4g+1)=2n+13(4g+1) = 2n+1, we have 3−1≡4g+1(mod2n)3^{-1} \equiv 4g+1 \pmod{2n}: colour c+1c+1 is carried by class a+(4g+1)a + (4g+1) and colour c+2c+2 by class a+(8g+2)a + (8g+2).

Window condition. By Lemma 2(b) with q=3q = 3, and since each class is a matching, we must show that for every aa the classes aa, a+(4g+1)a + (4g+1), a+(8g+2)a+(8g+2) are pairwise vertex-disjoint; as aa ranges over all of ℤ2n\mathbb Z_{2n} it suffices that for all aa

V(class(a))∩V(class(a+4g+1))=∅andV(class(a))∩V(class(a+8g+2))=∅V(\mathrm{class}(a)) \cap V(\mathrm{class}(a+4g+1)) = \emptyset \quad\text{and}\quad V(\mathrm{class}(a)) \cap V(\mathrm{class}(a+8g+2)) = \emptyset

(the pair (a+4g+1,a+8g+2)(a+4g+1, a+8g+2) is the first condition at a′=a+4g+1a' = a+4g+1).

Reduction to translates, with a=2i+εa = 2i+\varepsilon: - 4g+14g+1 is odd. If ε=0\varepsilon = 0: a+4g+1=2(i+2g)+1a + 4g+1 = 2(i+2g) + 1, class M1+i+2gM_1 + i + 2g. Condition: (V0+i)∩(V1+i+2g)=∅(V_0 + i) \cap (V_1 + i + 2g) = \emptyset, i.e. (C1) V0∩(V1+2g)=∅V_0 \cap (V_1 + 2g) = \emptyset. If ε=1\varepsilon = 1: a+4g+1=2(i+2g+1)a + 4g + 1 = 2(i + 2g + 1), class M0+i+2g+1M_0 + i + 2g + 1. Condition (C2) V1∩(V0+2g+1)=∅V_1 \cap (V_0 + 2g + 1) = \emptyset. - 8g+28g+2 is even: a+8g+2=2(i+4g+1)+εa + 8g + 2 = 2(i + 4g + 1) + \varepsilon, class Mε+i+4g+1M_\varepsilon + i + 4g+1. Condition Vε∩(Vε+4g+1)=∅V_\varepsilon \cap (V_\varepsilon + 4g+1) = \emptyset. Since 4g+1≡−2g(modn)4g + 1 \equiv -2g \pmod n, this is Vε∩(Vε−2g)=∅V_\varepsilon \cap (V_\varepsilon - 2g) = \emptyset, equivalently (translate by 2g2g) (C3) V0∩(V0+2g)=∅V_0 \cap (V_0 + 2g) = \emptyset and (C4) V1∩(V1+2g)=∅V_1 \cap (V_1 + 2g) = \emptyset.

Checks (all integers below are in [0,6g][0, 6g] unless reduced): - (C1) V1+2g={2g+1}∪[4g+2,6g]V_1 + 2g = \{2g+1\} \cup [4g+2, 6g]. V0={0}∪[2g+2,4g]V_0 = \{0\} \cup [2g+2, 4g]: 0∉0 \notin, 2g+1<2g+22g+1 \lt 2g+2, 4g<4g+24g \lt 4g+2. Disjoint. - (C2) V0+2g+1={2g+1}∪[4g+3,6g+1]={0,2g+1}∪[4g+3,6g]V_0 + 2g + 1 = \{2g+1\} \cup [4g+3, 6g+1] = \{0, 2g+1\} \cup [4g+3, 6g] (as 6g+1≡06g+1 \equiv 0). V1={1}∪[2g+2,4g]V_1 = \{1\} \cup [2g+2, 4g]: 1∉{0,2g+1}∪[4g+3,6g]1 \notin \{0, 2g+1\} \cup [4g+3,6g], and [2g+2,4g][2g+2, 4g] misses 00, 2g+12g+1 and [4g+3,6g][4g+3, 6g]. Disjoint. - (C3) V0+2g={2g}∪[4g+2,6g]V_0 + 2g = \{2g\} \cup [4g+2, 6g] versus {0}∪[2g+2,4g]\{0\} \cup [2g+2, 4g]. Disjoint. - (C4) V1+2g={2g+1}∪[4g+2,6g]V_1 + 2g = \{2g+1\} \cup [4g+2, 6g] versus {1}∪[2g+2,4g]\{1\} \cup [2g+2, 4g] (2g+1≠12g+1 \ne 1). Disjoint.

Hence cc is a (2n,3)(2n,3)-edge-colouring of GgG_g and, by Lemma 2(a), χ′c(Gg)≤2n/3\chi'_c(G_g) \le 2n/3.

(Remark: each window consists of three classes with 2g2g vertices each, i.e. it is a matching of size 3g3g covering all vertices but one. This is exactly the equality case of the averaging in Lemma 1.)

2.4 Lower bound and conclusion

nn is odd, so α′(Gg)≤(n−1)/2=3g\alpha'(G_g) \le (n-1)/2 = 3g; the edges {2j,2j+1}\{2j, 2j+1\}, 0≤j<3g0 \le j \lt 3g, have length 1∈Sg1 \in S_g and form a matching of size 3g3g, so α′(Gg)=3g\alpha'(G_g) = 3g. By Lemma 1,

χ′c(Gg)≥2gn3g=2n3.\chi'_c(G_g) \ \ge\ \frac{2gn}{3g} = \frac{2n}{3} .

Together with 2.3, χ′c(Gg)=2n/3=4g+2/3\chi'_c(G_g) = 2n/3 = 4g + 2/3. (Of course also χ′f(Gg)=2n/3\chi'_f(G_g) = 2n/3.)

2.5 Connectivity

Let GG be a connected, non-complete graph with vertex connectivity κ\kappa. For F⊆VF \subseteq V put N(F)={v∉F:v has a neighbour in F}N(F) = \{v \notin F : v \text{ has a neighbour in } F\} and F‾=V\(F∪N(F))\bar F = V \setminus (F \cup N(F)). If F≠∅≠F‾F \ne \emptyset \ne \bar F then N(F)N(F) separates FF from F‾\bar F, so |N(F)|≥κ|N(F)| \ge \kappa.

Definition. A fragment is a set FF with F≠∅F \ne \emptyset, F‾≠∅\bar F \ne \emptyset and |N(F)|=κ|N(F)| = \kappa. An atom is a fragment of minimum cardinality; this cardinality is denoted α0\alpha_0. (Fragments exist: for a minimum separator TT and a component FF of G−TG - T, N(F)⊆TN(F) \subseteq T and F‾⊇V\(F∪T)≠∅\bar F \supseteq V \setminus (F \cup T) \ne \emptyset, so |N(F)|=κ|N(F)| = \kappa.)

Two facts used below: (i) if FF is a fragment then so is F‾\bar F, with N(F‾)=N(F)N(\bar F) = N(F) and F‾‾=F\bar{\bar F} = F — indeed no vertex of F‾\bar F is adjacent to FF, so N(F‾)⊆N(F)N(\bar F) \subseteq N(F), and FF lies outside F‾∪N(F‾)\bar F \cup N(\bar F), so |N(F‾)|≥κ|N(\bar F)| \ge \kappa; in particular |F‾|≥α0|\bar F| \ge \alpha_0. (ii) If {x}\{x\} is an atom then κ=|N({x})|=degx\kappa = |N(\{x\})| = \deg x.

Lemma 3 (Watkins 1970; Mader). Distinct atoms are disjoint.

Proof (included for completeness). Let A,BA, B be atoms with A∩B≠∅A \cap B \ne \emptyset. Partition VV by the rows R1=AR_1 = A, R2=N(A)R_2 = N(A), R3=A‾R_3 = \bar A and the columns C1=BC_1 = B, C2=N(B)C_2 = N(B), C3=B‾C_3 = \bar B; let Xjk=Rj∩CkX_{jk} = R_j \cap C_k and xjk=|Xjk|x_{jk} = |X_{jk}|. A neighbour of a vertex of AA lies in R1∪R2R_1 \cup R_2, a neighbour of a vertex of A‾\bar A in R2∪R3R_2 \cup R_3, and similarly for columns. Hence

N(X11)⊆X12∪X21∪X22,N(X33)⊆X23∪X32∪X22,N(X13)⊆X12∪X22∪X23,N(X31)⊆X21∪X22∪X32,N(X_{11}) \subseteq X_{12} \cup X_{21} \cup X_{22},\quad N(X_{33}) \subseteq X_{23} \cup X_{32} \cup X_{22},\quad N(X_{13}) \subseteq X_{12} \cup X_{22} \cup X_{23},\quad N(X_{31}) \subseteq X_{21} \cup X_{22} \cup X_{32},

and in each case the "opposite corner" (X33X_{33} for X11X_{11}, X31X_{31} for X13X_{13}, …) lies outside X∪N(X)X \cup N(X). Put s=x12+x21+x22s = x_{12}+x_{21}+x_{22}, t=x23+x32+x22t = x_{23}+x_{32}+x_{22}; then s+t=|N(A)|+|N(B)|=2κs + t = |N(A)| + |N(B)| = 2\kappa; likewise u=x12+x22+x23u = x_{12}+x_{22}+x_{23} and v=x21+x22+x32v = x_{21}+x_{22}+x_{32} satisfy u+v=2κu + v = 2\kappa.

If s≤κs \le \kappa: X11≠∅X_{11} \ne \emptyset and A‾≠∅\bar A \ne \emptyset lies outside X11∪N(X11)X_{11} \cup N(X_{11}), so κ≤|N(X11)|≤s≤κ\kappa \le |N(X_{11})| \le s \le \kappa and X11X_{11} is a fragment; |X11|≥α0=|A|=|B||X_{11}| \ge \alpha_0 = |A| = |B| forces A=X11=BA = X_{11} = B.

If s>κs \gt \kappa, then t<κt \lt \kappa. If X33≠∅X_{33} \ne \emptyset, then X11≠∅X_{11} \ne \emptyset lies outside X33∪N(X33)X_{33} \cup N(X_{33}), so κ≤|N(X33)|≤t<κ\kappa \le |N(X_{33})| \le t \lt \kappa, impossible; so X33=∅X_{33} = \emptyset. From t<κ=|N(A)|=x21+x22+x23t \lt \kappa = |N(A)| = x_{21}+x_{22}+x_{23} we get x32<x21≤|B|−x11<α0x_{32} \lt x_{21} \le |B| - x_{11} \lt \alpha_0, and from t<κ=|N(B)|=x12+x22+x32t \lt \kappa = |N(B)| = x_{12}+x_{22}+x_{32} we get x23<x12<α0x_{23} \lt x_{12} \lt \alpha_0. Now A‾=X31∪X32\bar A = X_{31} \cup X_{32} and |A‾|≥α0>x32|\bar A| \ge \alpha_0 \gt x_{32} by (i), so X31≠∅X_{31} \ne \emptyset; likewise B‾=X13∪X23\bar B = X_{13} \cup X_{23} gives X13≠∅X_{13} \ne \emptyset. Each of X13,X31X_{13}, X_{31} lies outside the other's closed neighbourhood, so |N(X13)|,|N(X31)|≥κ|N(X_{13})|, |N(X_{31})| \ge \kappa, while |N(X13)|+|N(X31)|≤u+v=2κ|N(X_{13})| + |N(X_{31})| \le u + v = 2\kappa. Hence |N(X13)|=κ|N(X_{13})| = \kappa, X13X_{13} is a fragment contained in AA, so X13=AX_{13} = A, contradicting X11≠∅X_{11} \ne \emptyset. ▫\square

Lemma 4 (atoms of Cayley graphs; cf. Hamidoune 1977). Let G=Cay(Γ,T)G = \mathrm{Cay}(\Gamma, T) be a connected non-complete Cayley graph of a finite group Γ\Gamma (here Γ=ℤn\Gamma = \mathbb Z_n, written additively). Then the atom containing 00 exists, is unique, and is a subgroup of Γ\Gamma.

Proof. Automorphisms map fragments to fragments and atoms to atoms. Translations x↦x+hx \mapsto x + h are automorphisms. If A′A' is any atom and a∈A′a \in A', then A′−aA' - a is an atom containing 00; by Lemma 3 it is the unique one, call it AA. For h∈Ah \in A, A−hA - h is an atom containing 00, so A−h=AA - h = A. Thus a−h∈Aa - h \in A for all a,h∈Aa, h \in A, and A∋0A \ni 0 is a subgroup. ▫\square

(Lemma 3 says the atoms form a system of blocks of imprimitivity of Aut(G)\mathrm{Aut}(G) when GG is vertex-transitive — Watkins' theorem; Lemma 4 is the special case of a regular subgroup.)

Proposition 5. κ(Gg)=4g\kappa(G_g) = 4g for every g≥2g \ge 2.

Proof. Let HH be the atom containing 00; by Lemma 4, H=d′ℤnH = d'\mathbb Z_n for a divisor d′d' of nn, of index d′d' and order n/d′n/d'. d′=1d' = 1 is impossible (H‾\bar H would be empty). - If 2≤d′≤2g−12 \le d' \le 2g-1: the cosets of HH are H+jH + j, 0≤j≤d′−10 \le j \le d'-1, and every j∈[1,d′−1]⊆[1,2g−2]⊆Sgj \in [1, d'-1] \subseteq [1, 2g-2] \subseteq S_g. So every x∉Hx \notin H is h+jh + j with h∈Hh \in H, j∈Sgj \in S_g, hence adjacent to hh: H∪N(H)=ℤnH \cup N(H) = \mathbb Z_n, H‾=∅\bar H = \emptyset, contradicting that HH is a fragment. - If d′≥2gd' \ge 2g: |H|=n/d′≤(6g+1)/(2g)<4|H| = n/d' \le (6g+1)/(2g) \lt 4, and |H||H| divides n=6g+1n = 6g+1, which is odd and ≡1(mod3)\equiv 1 \pmod 3; hence |H|=1|H| = 1.

So H={0}H = \{0\} is an atom and κ=deg0=4g\kappa = \deg 0 = 4g by (ii). ▫\square

(Edge connectivity is then also 4g4g, as κ≤λ≤δ\kappa \le \lambda \le \delta.)

This completes the proof of Theorem 1. ◼\blacksquare

2.6 Proof of Theorem 2 (Δ=18\Delta = 18)

H=C25(S)H = C_{25}(S), S={1,2,3,7,8,9,10,11,12}S = \{1,2,3,7,8,9,10,11,12\}: nine distinct lengths in [1,12][1,12], so HH is simple, 18-regular, |E|=225|E| = 225. By 2.2-type reasoning, the edges of each length form one translation orbit of size 25.

Colouring (found by search/cyc2.py: python3 search/cyc2.py 100 12,3). Base classes (each a matching of 3 edges):

B0={{0,1},{2,9},{10,24}},B1={{0,2},{1,10},{11,24}},B2={{0,3},{1,11},{2,10}}B_0 = \{\{0,1\},\{2,9\},\{10,24\}\},\quad B_1 = \{\{0,2\},\{1,10\},\{11,24\}\},\quad B_2 = \{\{0,3\},\{1,11\},\{2,10\}\}

with lengths {1,7,11}\{1,7,11\}, {2,9,12}\{2,9,12\}, {3,10,8}\{3,10,8\} — together exactly SS, each once. Vertex sets W0={0,1,2,9,10,24}W_0 = \{0,1,2,9,10,24\}, W1={0,1,2,10,11,24}W_1 = \{0,1,2,10,11,24\}, W2={0,1,2,3,10,11}W_2 = \{0,1,2,3,10,11\}. For a∈ℤ75a \in \mathbb Z_{75} write a=3s+ra = 3s + r, r∈{0,1,2}r \in \{0,1,2\}, s∈ℤ25s \in \mathbb Z_{25}, and put class(a)=Br+s\mathrm{class}(a) = B_r + s, coloured 4amod754a \bmod 75 (gcd(4,75)=1\gcd(4,75) = 1). The 75 classes partition E(H)E(H) (each length occurs in exactly one BrB_r, and its 25 translates are distinct).

4−1≡19(mod75)4^{-1} \equiv 19 \pmod{75}, so a window of 4 consecutive colours is {class(a),class(a+19),class(a+38),class(a+57)}\{\mathrm{class}(a), \mathrm{class}(a+19), \mathrm{class}(a+38), \mathrm{class}(a+57)\}. With 19=3⋅6+119 = 3\cdot 6 + 1, 38=3⋅12+238 = 3 \cdot 12 + 2, 57=3⋅1957 = 3 \cdot 19, the condition "class aa disjoint from class a+19ta + 19t for t=1,2,3t = 1,2,3 and all aa" becomes Wr∩(Wr′+δ)=∅W_r \cap (W_{r'} + \delta) = \emptyset for the nine triples (r,r′,δ)(r, r', \delta):

(0,1,6),(1,2,6),(2,0,7),(0,2,12),(1,0,13),(2,1,13),(0,0,19),(1,1,19),(2,2,19).(0,1,6),\ (1,2,6),\ (2,0,7),\ (0,2,12),\ (1,0,13),\ (2,1,13),\ (0,0,19),\ (1,1,19),\ (2,2,19).

Check: W1+6={5,6,7,8,16,17}W_1+6 = \{5,6,7,8,16,17\}, W2+6={6,7,8,9,16,17}W_2+6 = \{6,7,8,9,16,17\}, W0+7={6,7,8,9,16,17}W_0+7 = \{6,7,8,9,16,17\}, W2+12={12,13,14,15,22,23}W_2+12 = \{12,13,14,15,22,23\}, W0+13={12,13,14,15,22,23}W_0+13 = \{12,13,14,15,22,23\}, W1+13={12,13,14,15,23,24}W_1+13 = \{12,13,14,15,23,24\}, W0+19={3,4,18,19,20,21}W_0+19 = \{3,4,18,19,20,21\}, W1+19={4,5,18,19,20,21}W_1+19 = \{4,5,18,19,20,21\}, W2+19={4,5,19,20,21,22}W_2+19 = \{4,5,19,20,21,22\}, and each is disjoint from the corresponding WrW_r (first entry of the triple): e.g. W2+6∋9∉W1W_2+6 \ni 9 \notin W_1, W0+7∋9∉W2W_0+7 \ni 9 \notin W_2, W1+13∋24∉W2W_1+13 \ni 24 \notin W_2, W0+19∋3∉W0W_0+19 \ni 3 \notin W_0, and all other elements of the nine translates lie in [4,8]∪[12,23][4,8] \cup [12,23], which no WrW_r meets. So this is a (75,4)(75,4)-edge-colouring and χ′c(H)≤75/4\chi'_c(H) \le 75/4. Lower bound: α′(H)=12\alpha'(H) = 12 (matching {2j,2j+1}\{2j,2j+1\}), 225/12=75/4225/12 = 75/4.

Connectivity. The subgroups of ℤ25\mathbb Z_{25} are {0},5ℤ25,ℤ25\{0\}, 5\mathbb Z_{25}, \mathbb Z_{25}. For 5ℤ255\mathbb Z_{25}: Smod5⊇{1,2,3,4}S \bmod 5 \supseteq \{1,2,3,4\} (1,2,3,91, 2, 3, 9), so every non-zero coset is met by SS and, as in Proposition 5, it is not a fragment. Hence the atom at 00 is {0}\{0\} and κ(H)=18\kappa(H) = 18. ◼\blacksquare

3. Consequences for the questions of Mazák–Zrubák

The remark "for any Δ≥8\Delta \ge 8 we don't even know a single graph". Answered for every Δ≡0(mod4)\Delta \equiv 0 \pmod 4 with Δ≥8\Delta \ge 8 (Theorem 1, value Δ+2/3\Delta + 2/3) and for Δ=18\Delta = 18 (Theorem 2, value Δ+3/4\Delta + 3/4). The graphs are simple, regular, and of connectivity Δ\Delta. For Δ≥8\Delta \ge 8 with Δ≢0(mod4)\Delta \not\equiv 0 \pmod 4, Δ≠18\Delta \ne 18, Theorems 1–2 give nothing; Section 7 (computer-certified, not a general proof) adds the non-regular cases Δ=21\Delta = 21 and Δ∈{4g+1,4g+2:6≤g≤13}\Delta \in \{4g+1, 4g+2 : 6 \le g \le 13\} and the regular case Δ=24\Delta = 24, value Δ+3/4\Delta + 3/4.

Problem 6. Read literally ("at least d+1/2d + 1/2", upper end d+1d+1 allowed), Problem 6 is trivially answered for every even dd by Kd+1K_{d+1} (which is dd-connected and has χ′c=d+1\chi'_c = d+1, as Mazák–Zrubák themselves note in Section 4; they also note that C7(1,2)C_7(1,2) is 4-connected with χ′c=5\chi'_c = 5). The non-trivial reading, suggested by the context (the cited examples have χ′c=d+1/2\chi'_c = d + 1/2 exactly, and the paper is about values strictly below Δ+1\Delta + 1), asks for χ′c∈[d+1/2,d+1)\chi'_c \in [d + 1/2, d+1). For that reading Theorems 1–2 give an affirmative answer for d∈{8,12,16,20,…}∪{18}d \in \{8, 12, 16, 20, \dots\} \cup \{18\}, with χ′c−d∈{2/3,3/4}\chi'_c - d \in \{2/3, 3/4\}, strictly inside (1/2,1)(1/2, 1) (Section 7.2 adds a second d=18d = 18 example, C31(1,2,3,7,…,12)C_{31}(1,2,3,7,\dots,12) with χ′c=93/5\chi'_c = 93/5). The context also supports a third reading, χ′c=d+1/2\chi'_c = d + 1/2 exactly (the cited examples for d=3,4d = 3, 4 have exactly this value). Theorems 1–2 do not answer that reading: our values are d+2/3d + 2/3, d+3/4d + 3/4, d+3/5d + 3/5, never d+1/2d + 1/2; it remains open here for every d≥5d \ge 5. Known before (per the paper): d=3,4d = 3, 4. Open (as far as this note goes): odd d≥5d \ge 5 and even d≥6d \ge 6 with d≢0(mod4)d \not\equiv 0 \pmod 4, d≠18d \ne 18. Note that for odd dd a dd-regular graph has even order, so the overfull mechanism used here (odd order) is unavailable.

Problem 7. Not answered. Our denominators are q=3q = 3 (all Δ≡0mod4\Delta \equiv 0 \bmod 4, Δ≥8\Delta \ge 8) and q=4q = 4 (Δ=18\Delta = 18); the paper already has q=3,4,5q = 3, 4, 5 (at Δ≤6\Delta \le 6). What is new is that q=3q = 3 is realised with arbitrarily large Δ\Delta by simple, regular, maximally connected graphs, and q=4q = 4 at Δ=18\Delta = 18. In addition (Section 7.2, computer-certified, checked by the referee), C31(1,2,3,7,8,9,10,11,12)C_{31}(1,2,3,7,8,9,10,11,12) is 18-regular, 18-connected with χ′c=93/5=Δ+3/5\chi'_c = 93/5 = \Delta + 3/5: denominator 5 for a simple regular graph (the paper has q=5q = 5 only as 23/523/5, for multigraphs with Δ=4\Delta = 4). This still says nothing about q≥6q \ge 6.

A general remark (elementary). If GG is Δ\Delta-regular of odd order nn then Lemma 1 gives χ′c(G)≥Δn/(n−1)=Δ+Δ/(n−1)\chi'_c(G) \ge \Delta n/(n-1) = \Delta + \Delta/(n-1), which is >Δ+1/2\gt \Delta + 1/2 as soon as n≤2Δn \le 2\Delta; and χ′c≤χ′≤Δ+1\chi'_c \le \chi' \le \Delta + 1 (Vizing). So dense odd-order regular graphs automatically have χ′c\chi'_c in the closed upper half; the whole difficulty is to show χ′c<Δ+1\chi'_c \lt \Delta + 1 (e.g. KΔ+1K_{\Delta+1} has χ′c=Δ+1\chi'_c = \Delta+1). The constructions above do this by exhibiting a colouring meeting the fractional bound exactly ("perfect" colouring: every window of qq consecutive classes is a near-perfect matching).

4. What is new

  • An explicit infinite family of simple Δ\Delta-regular, Δ\Delta-connected circulants with χ′c=Δ+2/3\chi'_c = \Delta + 2/3, one for every Δ≡0(mod4)\Delta \equiv 0 \pmod 4, Δ≥8\Delta \ge 8; plus one with Δ=18\Delta = 18, χ′c=Δ+3/4\chi'_c = \Delta + 3/4. According to Mazák–Zrubák (March 2026) no graph with Δ≥8\Delta \ge 8 and χ′c∈(Δ+1/2,Δ+1)\chi'_c \in (\Delta + 1/2, \Delta+1) was known. We did not perform an exhaustive literature search beyond that paper and a few web searches (which found nothing more recent on this question).
  • The proof method: "perfect" circular colourings in which every window of qq consecutive colour classes misses exactly one vertex, so that the trivial lower bound |E|/α′|E|/\alpha' is attained; for circulants these can be sought with a cyclic ansatz (classes indexed by ℤp\mathbb Z_p, translation-equivariant).
  • Nothing new is claimed about atoms or connectivity; Lemmas 3–4 are classical and reproved only for completeness.

5. Verification

verify.py (standard library only; run python3 verify.py, about 0.3 s) checks, for g=2,…,30g = 2,\dots,30: the circulant is simple and 4g4g-regular; the 2n2n classes partition the edge set (each edge exactly once); a↦3aa \mapsto 3a is a bijection of ℤ2n\mathbb Z_{2n} and 3(4g+1)≡13(4g+1) \equiv 1; every class is a matching; the colouring is a (2n,3)(2n,3)-colouring, checked both per vertex (cyclically sorted incident colours differ by ≥3\ge 3) and per window (every 3 consecutive classes are pairwise vertex-disjoint); the matching {2j,2j+1}\{2j,2j+1\} exists, so α′=(n−1)/2\alpha' = (n-1)/2, and |E|/α′=2n/3=p/q|E|/\alpha' = 2n/3 = p/q. Vertex connectivity is computed by its own max-flow routine (vertex splitting, BFS augmenting paths): κ(Gg)=4g\kappa(G_g) = 4g for g=2,3,4g = 2,3,4 over all non-adjacent pairs and for g=5,…,8g = 5,\dots,8 over pairs (0,t)(0,t) (sufficient by vertex-transitivity). The same checks are made for Theorem 2 ((75,4)(75,4)-colouring, |E|/α′=75/4|E|/\alpha' = 75/4, κ=18\kappa = 18 over all pairs). Output ends with ALL CHECKS PASSED. The max-flow routine was cross-checked against networkx.node_connectivity on seven circulants (outside verify.py).

Referee pass. One independent model referee (report review/REVIEW.md) checked by hand: Lemmas 1–2; the classes, lengths and partition in 2.3; 3−1≡4g+13^{-1} \equiv 4g+1 and the reduction to (C1)–(C4) and each of (C1)–(C4); α′=3g\alpha' = 3g; Lemma 3 line by line, Lemma 4, Proposition 5 and the atom arguments for ℤ25,ℤ31,ℤ33\mathbb Z_{25}, \mathbb Z_{31}, \mathbb Z_{33}; the nine translate conditions of Theorem 2; (C1)–(C4) for the Family B vertex sets; the Section 7 lemmas; the quotations from Mazák–Zrubák. Independent computations (own code, networkx for α′\alpha' and κ\kappa, not importing ours): Theorem 1 colourings for g=2..40g = 2..40 (α′\alpha' by max-matching for g≤12g \le 12), κ(Gg)=4g\kappa(G_g) = 4g for g=2..7g = 2..7, κ=18,18,24\kappa = 18, 18, 24 for C25,C31,C33C_{25}, C_{31}, C_{33}, κ(C7(1,2))=4\kappa(C_7(1,2)) = 4; all Part 2 certificates rebuilt with Δ\Delta, δ\delta, α′\alpha' and |E|/α′=p/q|E|/\alpha' = p/q; exhaustive confirmation that the Family B base problem is unsolvable for g=3,4,5g = 3,4,5 and solvable for g=6g = 6; brute-force confirmation of UNSAT for cyclic (q,r,g)=(4,3,1),(5,3,1),(5,4,1)(q,r,g) = (4,3,1), (5,3,1), (5,4,1) (the other UNSAT claims of 7.4 were not re-checked); 60 random insertions (both forms) into Family B bases passed and 60 negative controls failed. No errors were found; the gaps it listed (mirror form, edge-disjointness for several insertions, wording in 7.1, the reading χ′c=d+1/2\chi'_c = d + 1/2 of Problem 6, mention of C31C_{31} in Section 3) are fixed in this version. Its scripts are in review/: check.py (networkx + standard library; run python3 check.py fam|kappa|part2) and extra.py (imports check.py; standard library otherwise; run python3 extra.py famB|g1, and its function insertion_famB() for the insertion tests); both read the certificate file data/part2_certificates.json by a path relative to their own folder. All of these were re-run successfully here.

6. Sources

Marks: † = read only through a summary/snippet (fetch tool or secondary source), not the primary text.

  1. J. Mazák, F. Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822v1, 9 March 2026, https://arxiv.org/abs/2603.08822 . Quotes above were obtained from the HTML version through a web-fetch tool that returns short verbatim excerpts; they were not compared with the PDF character by character. †(partially)
  2. A. Hackmann, A. Kemnitz, The circular chromatic index, Discrete Math. 286 (2004) 89–93 — reference [11] of (1), cited there for χ′c≥|E|/α′\chi'_c \ge |E|/\alpha'. † (not read; Lemma 1 is proved here directly)
  3. X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371–410, doi:10.1016/S0012-365X(00)00217-X. † (bibliographic data only; standard facts χf≤χc\chi_f \le \chi_c, χc\chi_c attained by a (k,d)(k,d)-colouring; not needed for the proof)
  4. A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551–559. † (origin of (k,d)(k,d)-colourings; not needed)
  5. M. E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23–29, doi:10.1016/S0021-9800(70)80005-9. † — its Theorem "in a connected vertex-transitive graph, distinct atoms are vertex-disjoint" is as stated in D. W. Morris et al.'s note https://www.cs.uleth.ca/~morris/Research/SpecialFamily.pdf (Theorem 1.1 there, attributed to Watkins). Lemma 3 above is proved independently.
  6. W. Mader — the atom lemma is often attributed jointly to Mader (early 1970s, Arch. Math.). † (exact reference not verified)
  7. Y. O. Hamidoune, Sur les atomes d'un graphe orienté, C. R. Acad. Sci. Paris Sér. A 284 (1977) 1253–1256 (bibliographic data from the reference list of arXiv:math/0603504). † (content not read; Lemma 4 is proved here directly)
  8. M.-Z. quote Lukoťka–Mazák, Cubic graphs with given circular chromatic index (2010), for the d=3d = 3 case of Problem 6. †

7. Further searches (Part 2; computer-certified examples, no new general theorem)

All statements here are verified by verify_part2.py (standard library; reads data/part2_certificates.json; prints ALL PART 2 CHECKS PASSED). "Perfect" colouring: a (p,q)(p,q)-colouring of a graph of odd order n=2m+1n = 2m+1 in which every window of qq consecutive classes is a matching of size mm; then χ′c=|E|/m=p/q\chi'_c = |E|/m = p/q exactly by Lemmas 1–2. Search scripts are in search/ (SAT via python-sat/CaDiCaL; work log search/LOG.md).

7.1 A structural lemma (proved, elementary). In a perfect (p,q)(p,q)-colouring let xcx_c be the vertex missed by window cc. Since window c+1c+1 = window cc minus class cc plus class c+qc+q, we get V(Ec+q)=(V(Ec)∪{xc})\{xc+1}V(E_{c+q}) = (V(E_c) \cup \{x_c\}) \setminus \{x_{c+1}\}. In the cyclic ansatz of search/cyc2.py (class(a+r)(a+r) = class(a)+1(a)+1, colour qaqa) colour c+qc+q corresponds to a+1a+1, so consecutive base vertex sets differ by at most one exchanged vertex, and after rr steps |(W0+1)\W0|≤r|(W_0 + 1) \setminus W_0| \le r (at most rr exchanges). Since for ∅≠W≠ℤn\emptyset \ne W \ne \mathbb Z_n the number of maximal cyclic runs of WW equals |{x∈W:x+1∉W}|=|(W+1)\W||\{x \in W : x+1 \notin W\}| = |(W+1) \setminus W|: each base vertex set is a union of at most rr cyclic intervals. Adding these implied constraints sped the SAT search up by about two orders of magnitude (e.g. q=4,g=3q=4,g=3: 8.5 s to 0.1 s).

7.2 New regular examples (cyclic ansatz), all with κ=Δ\kappa = \Delta (atom argument of 2.5, and max-flow): - C31(1,2,3,7,8,9,10,11,12)C_{31}(1,2,3,7,8,9,10,11,12): 18-regular, χ′c=93/5=Δ+3/5\chi'_c = 93/5 = \Delta + 3/5. Denominator 5 with a simple regular graph (Δ=18\Delta = 18); Mazák–Zrubák have q=5q = 5 only for multigraphs with Δ=4\Delta = 4 (23/523/5). Base classes B0={{0,11},{1,2},{3,10}}B_0=\{\{0,11\},\{1,2\},\{3,10\}\}, B1={{0,3},{1,11},{2,10}}B_1=\{\{0,3\},\{1,11\},\{2,10\}\}, B2={{0,12},{1,3},{2,11}}B_2=\{\{0,12\},\{1,3\},\{2,11\}\}, class(3s+ρ)=Bρ+s(3s+\rho) = B_\rho + s, colour 5amod935a \bmod 93. (n=31n = 31 is prime, so κ=18\kappa = 18 by Lemma 4.) Note: same connection set as Theorem 2 but on 31 vertices. - C33(1,2,3,4,5,9,10,…,15)C_{33}(1,2,3,4,5,9,10,\dots,15): 24-regular, χ′c=99/4\chi'_c = 99/4 (also covered by Theorem 1 as Δ≡0mod4\Delta \equiv 0 \bmod 4, but with q=4q = 4).

7.3 Non-regular examples, Δ≢0(mod4)\Delta \not\equiv 0 \pmod 4 (remark "Δ≥8\Delta \ge 8"). Insertion lemma (proved): if E0,…,Ep−1E_0,\dots,E_{p-1} is a perfect (p,q)(p,q)-colouring of GG and F1,…,FqF_1,\dots,F_q are matchings of the complement of GG with V(Fj)=V(Ec+j−1)V(F_j) = V(E_{c+j-1}), then inserting F1,…,FqF_1,\dots,F_q before colour cc gives a perfect (p+q,q)(p+q,q)-colouring of G+F1+…+FqG + F_1 + \dots + F_q (every new window is, as a family of vertex sets, a permutation of an old window). Mirror form: the same holds if instead V(Fj)=V(Ec−q+j−1)V(F_j) = V(E_{c-q+j-1}), i.e. the block copies the qq classes before the insertion point; proof: reversing the colour order c↦−cc \mapsto -c maps perfect (p,q)(p,q)-colourings to perfect (p,q)(p,q)-colourings and exchanges the two forms. Several insertions at once: if insertion points are separated by at least q−1q-1 old classes, no window meets two blocks, so the window structure is preserved; for the result to be a simple graph the blocks must in addition be pairwise edge-disjoint (each later block consists of matchings in the complement of GG plus the earlier blocks). Each insertion raises all degrees but one by 1. Family B: n=6g+1n = 6g+1, base (2n,3)(2n,3)-colouring with the cyclic ansatz and W0={0,1}∪[2g+3,4g]W_0 = \{0,1\} \cup [2g+3,4g], W1={1,2}∪[2g+3,4g]W_1 = \{1,2\} \cup [2g+3,4g] (these satisfy the four window conditions (C1)–(C4) of 2.3, checked by hand as there), and base graph without edges of length 1. Then the windows starting at colours 0 and 6 consist of unions of intervals of even length, perfectly matched by the length-1 edges {x,x+1}\{x,x+1\} with x∈{0}∪{3,5,…,6g−1}x \in \{0\}\cup\{3,5,\dots,6g-1\}, resp. x∈{1}∪{4,6,…,6g}x \in \{1\}\cup\{4,6,\dots,6g\} (disjoint sets of xx, so the two blocks are edge-disjoint, as the several-insertions hypothesis requires; the insertion points are 6 classes apart), giving Δ=4g+1\Delta = 4g+1 and 4g+24g+2 with χ′c=Δ+2/3\chi'_c = \Delta + 2/3. The only missing ingredient for a theorem for all gg is the base matching problem: perfect matchings of W0W_0 and W1W_1 with 2g2g pairwise distinct lengths, none equal to 1 (a Skolem/Langford-type problem; internal lengths must be exactly {2,…,2g−3}\{2,\dots,2g-3\}). Solved by SAT for 6≤g≤136 \le g \le 13 (certificates stored); UNSAT for g=3,4,5g = 3,4,5; g=14,15,16g = 14,15,16 not solved within 60 s; no uniform construction found yet (the obvious nested choices fail, checked by hand). Certified values: Δ∈{25,26,29,30,…,53,54}\Delta \in \{25,26,29,30,\dots,53,54\} (all Δ≡1,2mod4\Delta \equiv 1,2 \bmod 4 in [25,54][25,54]). Separately, a generalised insertion search gave a graph with Δ=21\Delta = 21, n=31n = 31, χ′c=65/3\chi'_c = 65/3; its block (inserted before colour 0) copies the vertex sets of colours 59, 60, 61 of the base, so it is an instance of the mirror form of the insertion lemma (it is also checked directly as a perfect (65,3)(65,3)-colouring by verify_part2.py).

7.4 Exhaustively excluded (UNSAT, cyclic ansatz with 0∈W00 \in W_0, i.e. complete up to translation): (q,r,g)(q,r,g) = (4,3,1), (4,3,2), (5,3,1), (5,4,1), (5,3,2), (5,4,2), (5,4,3), (6,5,1), (6,5,2), (7,4,1), (7,5,1), (7,6,1), (7,5,2), (8,5,1), (8,7,1), (9,5,1), (9,7,1), (9,8,1); undecided in 300 s: (7,4,2), (7,6,2), (8,5,2). Insertion into cyclic q=3q=3 bases (one block, inserted vertex sets free): UNSAT for g=2,3,4g = 2,3,4 (so no such graph for Δ=9,13,17\Delta = 9, 13, 17 of this form); g=5g = 5: D=2,3D = 2, 3 UNSAT with blocks 3 colours apart; Family B with D=3D = 3: UNSAT for g=6,7g = 6, 7 (blocks 6 apart); one block on the q=4,g=3q=4,g=3 base (Δ=19\Delta = 19): UNSAT. K2m+1K_{2m+1} minus (near-perfect matching + one edge), single-edge classes, value Δ+(m−1)/m\Delta + (m-1)/m: no perfect colouring for m=3,4m = 3, 4. A fully general SAT search for n=13n = 13, value 29/329/3 (Δ=9\Delta = 9) did not finish in 200 s.

Still open after this work: Problem 7 for q≥6q \ge 6; Δ≡3(mod4)\Delta \equiv 3 \pmod 4 (no example found); Δ∈{9,10,11,13,14,15,17,19,22,23}\Delta \in \{9,10,11,13,14,15,17,19,22,23\}; Problem 6 (non-trivial reading) for d≢0mod4d \not\equiv 0 \bmod 4, d≠18d \ne 18.