Lower bound for $R(5, 5)$ cyclic coloring

Question

I want a $K_5$-free $2$-coloring of $K_{42}$ to prove $R(5, 5) > 42$. The only construction I could find is from Exoo, G. (1989). A lower bound for R (5, 5). Journal of graph theory, 13(1), 97-98:

A cyclic coloring is one in which the vertices of $K_n$ are identified with the integers from $0$ to $n - 1$, and in which the color of an edge depends only on the numerical differences between its end-vertices. These differences are often called chord lengths. A cyclic coloring can be specified by giving the chord lengths (from $\mathbf{1}$ to $\mathbf{[n/2]}$) for each color.

Q1: Don't we need the chord lengths from $1$ to $n - 1$? How else will we know what color to assign to the edge $0 \leftrightarrow n - 1$, which has chord length $n - 1$?

---

The coloring of $K_{42}$ starts with a coloring of $K_{43}$. Assign the chord lengths $1, 2, 7, 10, 12, 13, 14, 16, 18, 20, 21$ to red and $3, 4, 5, 6, 8, 9, 11, 15, 17, 19$ to blue. The resulting $K_{43}$ has $0$ blue $K_5$s and $43$ red $K_5$s, which have vertices of the form $$\{i, i + 1, i + 2, i + 22, i + 23 \} \quad \text{for } i = 0, 1, \dots, 42$$

Q2: Does this use congruence classes mod $43$? When $i = 41$, the vertices would be $\{ 41, 42, 0, 20, 21 \}$?

---

The next step is to delete vertex $0$, producing a colored $K_{42}$ with only $43 - 5 = 38$ red $K_5$s. Finally, change the following edges from red to blue: $11 \leftrightarrow 32$ and $j \leftrightarrow j + 1$ for $j = 4, 5, 6, 7, 13, 14, 15, 16, 23, 24, 30, 33, 39, 40, 41$. One can verify with a computer that this coloring of $K_{42}$ is $K_5$-free.

I really want to see a picture of this coloring, but I can't find one.

Answer 1

Don't we need the chord lengths from $1$ to $n−1$? How else will we know what color to assign to the edge $0↔n−1$, which has chord length $n−1$?

This edge has length $n-1$ if we go around the circle "the long way", going $0, 1, 2, 3, \dots, n-1$. It has length only $1$ if we go around the circle the other way. So we actually assign length $1$ to such a chord.

There's two ways to think about these lengths:

1. The chord lengths are distances in the cycle graph $C_n$ (where the vertices are also labeled $0, 1, 2, \dots, n-1$, and which contains edges $i \leftrightarrow i+1$ and $n-1 \leftrightarrow 0$).
2. To find the chord length of the edge $i \leftrightarrow j$, take $i - j \bmod n$, but instead of using the residues $0, 1, \dots, n-1$ as usual, use the residues $-\lfloor \frac n2\rfloor, \dots, \lceil \frac n2 \rceil$. Then, take the absolute value.

Does this use congruence classes mod $43$? When $i=41$, the vertices would be $\{41,42,0,20,21\}$?

Yes. Because the chord lengths are computed modulo $43$, the cliques also have the same structure.

I really want to see a picture of this coloring, but I can't find one.

It's hard to think of a very enlightening way to draw the coloring. Here's a picture that might not be very helpful:

I've put the points in order around the circle, with the missing vertex $0$ at the top, and the rest going $1, 2, 3, \dots, 42$ in order clockwise. The edges that have been recolored from red to blue are shown darker and thicker than the rest.

Here is the graph6 encoding for the graph of the red edges:

>>graph6<<izGOSHBG[`hBhBs`\GRhAmcH\G\\GYmcMjhBt\G^Ts`}jhA]jhAnTs`jt\G\]jhBTymcMjt\G]jt\GVTimcLt]jhBmjt\GQynTs`dt]jhBdt]jhBQynTs`cmjt\GWdt]jhAAVTymcICmjt\GO

For example, we might use this to verify the lower bound in Mathematica as follows:

graph = ImportString[
  ">>graph6<<izGOSHBG[`hBhBs`\\GRhAmcH\\G\\\\GYmcMjhBt\\G^Ts`}jhA]\
jhAnTs`jt\\G\\]jhBTymcMjt\\G]jt\\GVTimcLt]jhBmjt\\GQynTs`dt]jhBdt]\
jhBQynTs`cmjt\\GWdt]jhAAVTymcICmjt\\GO", "Graph6"];
VertexCount[graph]
FindClique[graph]
FindClique[GraphComplement[graph]]

The expected output is 42 for the vertex count, a $4$-vertex clique {{1, 2, 3, 15}} for a largest clique in the graph, and a $4$-vertex clique {{1, 4, 5, 9}} for a largest clique in the complement.