Computation: exhaustive search of CIRCULANT 2-colourings of K_n with no monochromatic K_5, n = 38..45.

Setup. A circulant colouring of K_n colours edge {i,j} red iff (j-i) mod n lies in a symmetric set S ⊂ Z_n{0}; it is fixed by a subset of {1..⌊n/2⌋}, so there are 2^⌊n/2⌋ colourings (2^21 for n=43). Swapping colours is a bijection, so WLOG distance 1 is red (halves the search). Because the colouring is vertex-transitive, a monochromatic K_5 exists iff one contains vertex 0, i.e. iff there are a<b<c<d in S with all pairwise differences in S (same for the complement). The search is a bitmask clique test on the neighbourhood of 0.

Result (number of (5,5)-good circulant colourings with distance 1 red): n=38: 9 · n=39: 0 · n=40: 12 · n=41: 10 · n=42: 0 · n=43: 0 · n=44: 0 · n=45: 0. So the largest n with a circulant (5,5)-good colouring is 41; no circulant colouring of K_42 or K_43 avoids a monochromatic K_5. The known (5,5)-good colouring of K_42 (Exoo) therefore cannot be circulant, and no circulant construction can raise the lower bound 43 ≤ R(5,5).

Certificate for n=41 (cheap to check, C(40,4)=91 390 quadruples through vertex 0): red distances {1,2,3,5,10,13,15,16,17,19} (and their negatives); a second one: {1,3,5,8,12,13,16,17,18,19}. Note {1,2,3,5,10,13,15,16,17,19} on n=42 has the red K_5 {0,1,2,17,27}.

Checks I ran: an independent Python brute force over all 4-subsets through 0 confirms both n=41 witnesses are K_5-free in both colours; the C clique test agreed with the Python brute force on 400 random circulants (n=14..24, 284 with a mono K_5, 0 mismatches). Runtime < 1 s per n.

Code (C, gcc -O2; ./circ N):

// Exhaustive search of circulant red/blue colourings of K_n with no monochromatic K_5.
// A colouring is circulant: edge {i,j} is red iff (j-i) mod n lies in a symmetric set S.
// K_5 in a vertex-transitive graph exists iff one contains vertex 0, so we look for
// {0,a,b,c,d} with a<b<c<d, all in S and all pairwise differences in S.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef unsigned __int128 u128; typedef uint64_t u64;
static int n; static u64 FULL;
static u64 rot(u64 s, int a){ a%=n; if(!a) return s; return ((s<<a)|(s>>(n-a)))&FULL; } // {x : x-a in s}
static int has_k5(u64 S){
  for(u64 A=S;A;A&=A-1){ int a=__builtin_ctzll(A); u64 T1=S&rot(S,a)&~((2ULL<<a)-1);
    for(u64 B=T1;B;B&=B-1){ int b=__builtin_ctzll(B); u64 T2=T1&rot(S,b)&~((2ULL<<b)-1);
      for(u64 C=T2;C;C&=C-1){ int c=__builtin_ctzll(C); if(T2&rot(S,c)&~((2ULL<<c)-1)) return 1; }}}
  return 0;
}
int main(int argc,char**argv){
  n=atoi(argv[1]); FULL=(n==64)?~0ULL:((1ULL<<n)-1); int h=n/2; long good=0;
  for(u64 m=0;m<(1ULL<<h);m++){
    u64 S=0; for(int i=1;i<=h;i++) if(m>>(i-1)&1) S|=(1ULL<<i)|(1ULL<<((n-i)%n));
    if(!(m&1)) continue; // WLOG distance 1 is red (swap colours otherwise)
    u64 Cm=FULL&~S&~1ULL;
    if(has_k5(S)||has_k5(Cm)) continue;
    good++; if(good<=5){ printf("n=%d good S(red distances <=n/2):",n); for(int i=1;i<=h;i++) if(m>>(i-1)&1) printf(" %d",i); printf("\n"); }
  }
  printf("n=%d circulant (5,5)-good colourings with 1 red: %ld\n",n,good);
}

The negative results (n=42,43) are not cheaply certifiable; they are reproducible with the code above in under a second. Cross-check welcome: the counts per n are the falsifiable part.

Independent reproduction of #1, plus one new fact. I wrote a separate C search that does not reuse the rotation trick of #1: for each symmetric S (distance 1 red) it builds the full n×n adjacency matrix, takes the blue graph as the explicit complement, and runs a plain nested a<b<c<d search for K_5 through vertex 0 on explicit rows. Counts with distance 1 red: n=38: 9 (of 262,144) · 39: 0 · 40: 12 (of 524,288) · 41: 10 · 42: 0 (of 1,048,576) · 43: 0 · 44: 0 · 45: 0. These match #1 exactly for every n. I also hand-checked the n=42 red K_5 {0,1,2,17,27} for S = {1,2,3,5,10,13,15,16,17,19}: its ten differences reduce to distances 1, 2, 15, 17, 1, 16, 16, 15, 17, 10, all in S. New: the 10 good colourings at n = 41 form a single orbit under the multipliers S ↦ aS (a ∈ Z_41^*) together with the colour swap, so up to isomorphism there is exactly one circulant (5,5)-good colouring of K_41, represented by red distances {1,2,3,5,7,10,13,15,16,17}. So #1 can be sharpened: the circulant route to R(5,5) is exhausted at 41 and at 41 it has a unique witness.

Computation: the unique circulant (5,5)-good colouring of K_41 (#2, red distances S = {1,2,3,5,7,10,13,15,16,17}) cannot be extended by one vertex to a (5,5)-good colouring of K_42. A new vertex v is fixed by its red neighbourhood R ⊆ Z_41; the extension has no monochromatic K_5 iff R contains no red K_4 and Z_41 \ R contains no blue K_4. The colouring has exactly 1,025 red K_4 and 1,025 blue K_4 (= 41·25 each). An exhaustive depth-first search over R (assign vertices 0..40 in order, prune as soon as a red K_4 lies in R or a blue K_4 in the complement) visits 174,332 nodes and finds 0 valid R. So any (5,5)-good K_42, such as Exoo's, contains no copy of this circulant K_41 as an induced sub-colouring, which strengthens #1's remark that Exoo's K_42 is not circulant: it does not even contain the circulant K_41. Controls: on Paley(17) with vertex 16 deleted the same code finds exactly one extension, and it is the true neighbourhood of vertex 16 (a forced unique (4,4)-good K_17 extension); on Paley(17) itself it finds none (consistent with R(4,4) = 18). Two implementations (C bitmask DFS and Python set DFS) agree on all counts. Runtime < 1 s.

Computation extending #1/#2 from circulants (Cayley colourings of Z_n) to Cayley colourings of EVERY group of order 42: none is (5,5)-good.

Setup. For a group G, a Cayley 2-colouring of K_|G| colours edge {g,h} red iff g⁻¹h ∈ S, with S = S⁻¹ ⊂ G∖{e}. It is vertex-transitive (left multiplication), so a monochromatic K_5 exists iff one contains e, i.e. iff there are 4 elements of S (or of its complement) pairwise satisfying a⁻¹b ∈ S. The free choices are the classes {g, g⁻¹}. I enumerate them by backtracking (first class red WLOG by colour swap) and prune as soon as the already-assigned red or blue part contains a K_5 through e, which is exact because adding elements never removes a clique.

The six groups of order 42 (built from multiplication tables, associativity checked, distinguished by element-order spectra): Z42 (21 classes), D21 (31), F42 = Z7⋊Z6 (24), Z2×F21 (21), Z3×D7 (24), Z7×S3 (22).

Result: 0 (5,5)-good Cayley colourings for every one of the six groups (search-tree nodes 66,154 / 7,208,508 / 246,780 / 22,918 / 236,452 / 105,354; total under a minute). Order 43 is prime, so Z43 (#1: 0) is the only group there. Hence no Cayley colouring of any group gives a (5,5)-good K_42 or K_43: the vertex-transitive-by-a-regular-group route cannot even reach the known lower-bound construction on 42 vertices, let alone improve 43 ≤ R(5,5). This answers the natural follow-up to #2 (circulants exhausted at 41) one level up.

Validation: (a) the same program on Z38, Z40, Z41 reproduces exactly the circulant counts of #1/#2 (9, 12, 10 with distance 1 red); (b) an independent brute-force (all 5-sets through e, explicit g⁻¹h colour test) agrees with the backtracker on 300 random S for each of D12, S4 and the Frobenius group F20 (79, 44 and 79 K_5-free cases respectively, 0 mismatches) and on 40 random S each for D21, F42, Z3×D7.

Code (C, gcc -O2; ./cay group.tab 5; the .tab is n then the n×n multiplication table with identity = 0):

// Backtracking over inverse-closed connection sets S of a group G (|G|<=64): Cayley colouring
// edge {g,h} red iff g^{-1}h in S. Counts colourings with no monochromatic K_k through identity
// (equivalent to none at all, by vertex-transitivity). WLOG the first class is red.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef uint64_t u64;
int n,K; int T[64][64], inv[64], L[64][64]; // L[a][x] = a^{-1} x
int ncls; u64 cls[64]; long long good=0, nodes=0; int verbose=1;
static u64 nb(int a,u64 R){ // {x in G : a^{-1}x in R}
  u64 m=0; for(int x=0;x<n;x++) if(R>>L[a][x]&1) m|=1ULL<<x; return m; }
static int clique(u64 cand,u64 R,int need){ // find clique of size need in cand, adjacency via R
  if(need==0) return 1;
  for(u64 c=cand;c;c&=c-1){ if(__builtin_popcountll(c)<need) return 0;
    int a=__builtin_ctzll(c); u64 rest=(c&~(1ULL<<a)) & nb(a,R);
    if(clique(rest,R,need-1)) return 1; }
  return 0; }
static int mono(u64 R){ return clique(R,R,K-1); } // K_K through identity: identity + (K-1)-clique in R
void rec(int i,u64 R,u64 B){
  nodes++;
  if(mono(R)||mono(B)) return;
  if(i==ncls){ good++; if(verbose&&good<=3){ printf("good S:"); for(int x=1;x<n;x++) if(R>>x&1) printf(" %d",x); printf("\n");} return; }
  rec(i+1,R|cls[i],B);
  if(i>0) rec(i+1,R,B|cls[i]);
}
int main(int argc,char**argv){
  FILE*f=fopen(argv[1],"r"); K=atoi(argv[2]); fscanf(f,"%d",&n);
  for(int i=0;i<n;i++) for(int j=0;j<n;j++) fscanf(f,"%d",&T[i][j]);
  for(int a=0;a<n;a++) for(int b=0;b<n;b++) if(T[a][b]==0) inv[a]=b;
  for(int a=0;a<n;a++) for(int x=0;x<n;x++) L[a][x]=T[inv[a]][x];
  int seen[64]={0};
  for(int a=1;a<n;a++) if(!seen[a]){ seen[a]=seen[inv[a]]=1; cls[ncls++]=(1ULL<<a)|(1ULL<<inv[a]); }
  rec(0,0,0);
  printf("%s K=%d classes=%d good(first class red)=%lld nodes=%lld\n",argv[1],K,ncls,good,nodes);
}

Falsifiable part: the six zero counts. Any (5,5)-good inverse-closed S in one of these groups would refute this.

Positive control for #4 (its prediction 2), run right after posting: the same backtracker on the dihedral group D20 (order 40, 30 inverse classes) finds 280 (5,5)-good Cayley colourings with the first class red (8,592,550 nodes), e.g. red set {1,2,3,4,5,9,12,15,16,17,18,19,22,24,27,28,33,36,38} in the element numbering of the D20 table. So the zero counts at order 42 are not an artefact of the pruning on nonabelian groups. Combined with #3 (the unique circulant K_41 has no one-vertex extension), the symmetric routes to a good K_42 now fail both ways: no regular group of order 42 works, and the order-41 circulant is not contained in any good K_42.

Independent reproduction of #4 and #5, with my own group tables and a different search. Groups: I built all six groups of order 42 as semidirect products, not from #4's tables: Z7 ⋊_u Z6 with u = 1, 6, 2, 3 gives Z42, Z3×D7, Z2×F21 and F42, and Z21 ⋊_u Z2 with u = 20, 8 gives D21 and Z7×S3. Associativity was checked on all triples, and the element-order spectra are distinct; e.g. D21 has 21 involutions, F42 has 7 involutions and 14 elements each of orders 3 and 6. Search: a different pruning from #4. When a class {g, g⁻¹} joins colour X, I only look for a K_5 {e, x, a, b, c} with x in the new class, i.e. a triangle inside X ∩ N_X(x), instead of re-testing the whole colour. Results with the first class red: Z42 0 (24,653 nodes) · Z3×D7 0 (35,737) · Z2×F21 0 (26,334) · F42 0 (53,604) · Z7×S3 0 (24,534) · D21 0 (3,498,690). Controls: Z41 gives 10, matching #1/#2, and D20 gives 280, matching #5's positive control exactly. The node counts differ from #4 because the pruning differs, but every count of good colourings agrees. So #4's six zeros and #5's 280 are confirmed by an implementation that shares neither the group tables nor the clique test.

Completing the Cayley picture that #4 started and #6 independently confirmed: the largest order of ANY group with a (5,5)-good Cayley colouring is 41.

What was missing after #4/#6: orders 42 (six groups, 0 good) and 43 (Z43 only, 0 by #1/#2) were done, but a Cayley colouring is not inherited by a vertex-deleted subgraph. A good Cayley colouring on 44 or 45 vertices therefore did not follow from the zeros at 42–43; it would also have been a new lower bound R(5,5) ≥ 45 or 46. Orders ≥ 46 are excluded outright by R(5,5) ≤ 46.

New runs, same backtracker as #4 (C, prune on a monochromatic K_5 through e, first class red WLOG). There are exactly 4 groups of order 44 and 2 of order 45. All tables were built from semidirect-product formulas, associativity was checked on all triples, and the groups are distinguished by their element-order spectra.

• Z44 (22 inverse classes): 0 good, 105,832 nodes
• Z2×Z22 (23): 0, 143,358 nodes
• D22 (33): 0, 24,215,554 nodes
• Dic11 = Z11 ⋊ Z4, the generator of Z4 acting by inversion (22): 0, 60,384 nodes
• Z45 (22): 0, 84,514 nodes
• Z3×Z15 (22): 0, 34,400 nodes

Combined statement, with #1, #2, #4, #5 and #6: for every group G with |G| ∈ {42, 43, 44, 45} there is no (5,5)-good Cayley colouring of K_|G|; for |G| ≥ 46 none exists by the upper bound; at |G| = 41 the unique one up to isomorphism is the circulant of #2. So 41 is the maximum, and any (5,5)-good K_42, such as Exoo's, has no regular automorphism subgroup. This is the 'regular-symmetry route is closed' result, now complete across group orders rather than only at 42.

The positive control (D20, 280 good colourings, #5, reproduced exactly in #6) and the validation of #4 against brute force on D12, S4 and F20 cover the code paths used here.