Combinatorics - 1

Barbados Problem 33

Author: Pranav Deepak

Problem (Barb-33). Does there exist a $K_6$-free, odd-hole-free graph $G$ such that every coloring of $E(G)$ with two colors contains a monochromatic triangle?

Postscript (30/09/2026). After completing this write-up, I happened to check the 2026 Barbados problem list again and saw that Problem 33 had been updated and was no longer listed as open: this construction is already known; see Aleksandar Bikov’s Small minimal $(3,3)$-Ramsey graphs. This was nevertheless very expected, given the extensive classification of small $(3,3)$-Ramsey graphs. I have kept the proof here because it is self-contained and, I think, elegant.

1. The construction

Throughout, all arithmetic is performed in $\mathcal{V} := \mathbb{Z}/11\mathbb{Z}$. We fix the following subsets of $\mathcal{V}$:

$$\begin{aligned} \mathcal{N}_0 &= \{0,\pm 1\},\\ \mathcal{D}_R &= \{\pm 2,\pm 3\},\\ \mathcal{D}_B &= \{\pm 4,\pm 5\},\\ \mathcal{Q} &= \{2,4,6,8\},\\ \mathcal{S} &= \{0,2,5,8\}. \end{aligned}$$

Recall that a subset $\mathcal{D}$ of an additive group is sum-free if $x+y \notin \mathcal{D}$ whenever $x,y \in \mathcal{D}$.

We record the following elementary properties of the sets above:

$$\begin{aligned} \mathcal{D}_R \cap \mathcal{D}_B &= \varnothing,\\ \mathcal{D}_R \cup \mathcal{D}_B &= \mathcal{V} \setminus \mathcal{N}_0,\\ -\mathcal{D}_R &= \mathcal{D}_R,\\ -\mathcal{D}_B &= \mathcal{D}_B,\\ \mathcal{Q} \cap (-\mathcal{Q}) &= \varnothing,\\ \mathcal{Q} \cup (-\mathcal{Q}) &= \mathcal{V} \setminus \mathcal{N}_0. \end{aligned}$$

Both $\mathcal{D}_R$ and $\mathcal{D}_B$ are sum-free. Finally, if $a,b \in \mathcal{S}$ are distinct, then $b-a \notin \mathcal{N}_0$.

We call two distinct elements $a,b \in \mathcal{V}$ consecutive if $b-a \in \mathcal{N}_0$, and nonconsecutive otherwise.

Let $\mathsf{A}$ be the graph with vertex set $\mathcal{V}$ in which two distinct vertices $u,v$ are adjacent exactly when they are nonconsecutive. By construction, $\mathsf{A} \cong \overline{C_{11}}$.

Now let $\mathsf{H}$ be the graph obtained from $\mathsf{A}$ by adjoining a vertex $z$ with $N_{\mathsf{H}}(z)=\mathcal{S}$. We begin by verifying the structural properties of this construction.

For a graph $G$, let $\omega(G)$ denote its clique number.

Lemma 1. $\omega(\mathsf{A}) = 5$. Moreover, every induced path and every induced cycle in $\mathsf{A}$ has at most four vertices.

proof: A clique in $\mathsf{A}=\overline{C_{11}}$ is an independent set in $C_{11}$. Since an independent set in an $11$-cycle has at most $\lfloor 11/2 \rfloor=5$ vertices, $\omega(\mathsf{A}) \le 5$. On the other hand, $\{0,2,4,6,8\}$ induces a $K_5$ in $\mathsf{A}$, and hence $\omega(\mathsf{A})=5$.

Now, suppose $\mathsf{A}$ contains an induced cycle $C_{m}$ and let $M \sub \mathcal{V}$ be its vertex set. Indeed, $M$ induces $\overline{C_{m}}$ in $C_{11}$. Given that $\overline{C_{m}}$ is $m-3$-regular, and $C_{11}$ is $2$-regular, it follows that $m \le 5$. Finally, using $\overline{C_{5}} \cong C_{5}$, which is not a subgraph of $C_{11}$, we conclude that $m \le 4$.

Next, suppose $\mathsf{A}$ contains an induced path $P_{t}$. Each endpoint of $P_{t}$ has exactly $t-2$ non edges internally. Thus in $C_{11}$, each endpoint of $P_{t}$ has degree at least $t-2$. Of course $t-2 \le 2$. Hence $t \le 4$.

A hole is a vertex-induced cycle of length at least four. An odd hole is a hole of odd length.

Lemma 2. The graph $\mathsf{H}$ is $K_6$-free and odd-hole-free.

proof: By Lemma 1, $\mathsf{A}$ is $K_{6}$-free. Hence, any six-clique in $\mathsf{H}$ must contain the additional vertex $z$, but the degree of $z$ is four, so $\mathsf{H}$ is $K_{6}$-free.

By Lemma 1, every hole in $\mathsf{A}$ has length at most four. Thus an odd hole $C_m$ in $\mathsf{H}$ must contain the additional vertex $z$. Deleting $z$ leaves an induced path on $m-1$ vertices entirely in $\mathsf{A}$. Again by Lemma 1, $m-1 \le 4$, so $m \le 5$. Since an odd hole has length at least five, we must have $m=5$.

Write $C_5=zv_1v_2v_3v_4z$. Then $v_1,v_4 \in \mathcal{S}$, so they are nonconsecutive and hence adjacent in $\mathsf{A}$. Thus $v_1v_4$ is a chord of $C_5$, contrary to $C_5$ being induced.

2. Triangle-free colorings of $\mathsf{A}$

Throughout, a coloring of a graph $G$ means a map $f:E(G)\longrightarrow\{R,B\}$. We call the spanning subgraphs of $G$ with edge sets $f^{-1}(R)$ and $f^{-1}(B)$ the red subgraph and blue subgraph under $f$, respectively.

For adjacent vertices $u,v$, we call $u$ a red or blue neighbour of $v$ according to the color of $uv$.

A triangle is monochromatic if its three edges receive the same color, and a coloring is triangle-free if it contains no monochromatic triangle.

Lemma 3. Let $f$ be a coloring of $K_5$. Then $f$ is triangle-free exactly when its red and blue subgraphs are both isomorphic to $C_5$.

Moreover, if $f$ is triangle-free, then for every vertex $v$, the restriction of $f$ to $K_5-v$ has a red $P_4$ and a blue $P_4$, whose endpoints are exactly the red and blue neighbours of $v$ respectively.

proof: Suppose both color’s subgraphs are isomorphic to $C_{5}$ under $f$. Then since $C_{5}$ is a triangle-free graph, $f$ is triangle free.

Now, suppose $f$ is triangle free. No vertex can have three neighbours of the same color, say red. Otherwise, to avoid a triangle in the red subgraph, the three neighbours must form a blue triangle.

Thus the red and blue subgraphs are both $2$-regular, and thus each isomorphic to $C_{5}$.

Deleting any vertex of a $C_5$ leaves a $P_4$ whose endpoints are precisely the neighbours of the deleted vertex. Since the red and blue subgraphs under $f$ are both isomorphic to $C_5$, restricting $f$ to $K_5-v$ leaves a red $P_4$ and a blue $P_4$, whose endpoints are respectively the red and blue neighbours of $v$.

The partition $\mathcal{V}\setminus\mathcal{N}_0=\mathcal{D}_R\sqcup\mathcal{D}_B$ defines a coloring $\psi$ of $\mathsf{A}$, which we call the canonical difference coloring. Explicitly, for $uv\in E(\mathsf{A})$,

$$\psi(uv)= \begin{cases} R & \text{if } v-u\in\mathcal{D}_R,\\ B & \text{if } v-u\in\mathcal{D}_B. \end{cases}$$

Since $\mathcal{D}_R$ and $\mathcal{D}_B$ are closed under negation, this definition does not depend on the order of $u$ and $v$.

The coloring $\psi$ is triangle-free. Indeed, suppose $u,v,w$ formed a monochromatic triangle, and set $a=v-u$ and $b=w-v$. If the triangle were red, then $a,b\in\mathcal{D}_R$ and

$$a+b=w-u\in\mathcal{D}_R,$$

contradicting the sum-freeness of $\mathcal{D}_R$. The same argument with $\mathcal{D}_B$ rules out a blue triangle.

Below, we state the key rigidity result on triangle free colorings of $\mathsf{A}$.

Theorem 1. A coloring $f$ of $\mathsf{A}$ is triangle-free if and only if, up to exchanging the two colors, $f$ is equal to the canonical difference coloring $\psi$.

We defer the proof of Theorem 1 and first record its consequence for the graph $\mathsf{H}$.

Theorem 2. There is no triangle-free coloring of $\mathsf{H}$.

proof: (Supposing Theorem 1)

Let $f$ be a triangle free coloring of $\mathsf{H}$. Then, by Theorem 1 The restriction of $f$ to $\mathsf{A}$ is equal to $\psi$.

Recall that $\mathsf{H}$ is obtained from $\mathsf{A}$ by adjoining the vertex $z$, whose neighborhood is $\mathcal{S}=\{0,2,5,8\}$.

Now, consider the graph $K$ induced by $\mathcal{S}$ in $\mathsf{A}$. Since any two elements of $\mathcal{S}$ are nonconsecutive, and $|\mathcal{S}| = 4$ we have $K \cong K_{4}$. Since $f$ and $\psi$ agree on $K$, the red subgraph of $K$ under $f$ is the cycle $C_{4} = (0,2,5,8)$.

Since $z$ is adjacent to every vertex of $K$, the subgraph of $\mathsf{H}$ induced by $V(K)\cup\{z\}$ is isomorphic to $K_5$. The restriction of $f$ to this $K_5$ is triangle-free. Hence, by Lemma 3, deleting $z$ leaves a red $P_4$ on $K$. This contradicts the fact that the red subgraph of $K$ is isomorphic to $C_4$.

Combining Lemma 2 and Theorem 2 gives the main result.

Main Theorem. Let $C_{11}=v_0v_1\dots v_{10}v_0$, and let $\mathsf{H}$ be the graph obtained from $\overline{C_{11}}$ by adjoining a vertex $z$ whose neighborhood is $\{v_0,v_2,v_5,v_8\}$. Then $\mathsf{H}$ is $K_6$-free and odd-hole-free, and every coloring of its edges with two colors contains a monochromatic triangle.

It remains to prove Theorem 1.

The lemma that follows is motivated by the fact that $\mathsf{A}$ has lots of overlapping $5$-cliques, which we will exploit in proving Theorem 1.

First, For vertex-disjoint graphs $G_1$ and $G_2$, their join $G_1\vee G_2$ is obtained from their disjoint union by adding every edge between $V(G_1)$ and $V(G_2)$.

Lemma 4 (Small overlap lemma). Let $G=K_4\vee\overline{K_2}$, where the $K_4$-factor has vertex set $T$ and the $\overline{K_2}$-factor has vertex set $\{p,q\}$. If $f$ is a triangle-free coloring of $G$, then $f(pv)=f(qv)$ for every $v\in T$.

proof: Denote the $K_{5}$‘s induced by $T \cup \{p\}, T \cup \{q\}$ by $K_{p},K_{q}$ respectively, where $K_{p}-p$ and $K_{q}-q$ are equal to the $K_{4}$-factor of $G$. Thus, the restrictions of $f$ to $K_{p}-p$ and $K_{q}-q$ are also equal.

Therefore, given that $f$ is triangle free, by applying lemma 3 we conclude that the red and blue neighbourhoods of $p$ and $q$ (under $f$) are respectively equal.

We will compare an arbitrary triangle-free coloring $f$ of $\mathsf{A}$ with $\psi$ using a convenient system of coordinates on $E(\mathsf{A})$. In doing so, we will take full advantage of the additive structure on $V(\mathsf{A})=\mathcal{V}$.

Recall that $\mathcal{Q}=\{2,4,6,8\}$, and that $\mathcal{Q}$ and $-\mathcal{Q}$ partition $\mathcal{V}\setminus\mathcal{N}_0$. Consider the correspondence

$$(i,d)\longmapsto\{i,i+d\}, \qquad (i,d)\in\mathcal{V}\times\mathcal{Q}.$$

Since $d\notin\mathcal{N}_0$, the pair $\{i,i+d\}$ is an edge of $\mathsf{A}$. Conversely, if $\{u,v\}\in E(\mathsf{A})$, exactly one of $v-u$ and $u-v$ belongs to $\mathcal{Q}$. Thus every edge arises uniquely from this correspondence.

We henceforth write $\langle i,d\rangle$ for the edge $\{i,i+d\}$.

Under this identification, the same coloring $\psi$ admits a new prescription:

$$\psi(\langle i,d\rangle)= \begin{cases} R & \text{if } d\in\{2,8\},\\ B & \text{if } d\in\{4,6\}. \end{cases}$$

The next lemma translates the overlap of $5$-cliques in $\mathsf{A}$ into an algebraic invariance satisfied by every triangle-free coloring.

Lemma 5 (Big overlap lemma). Let $f$ be a triangle-free coloring of $\mathsf{A}$. Then, for every $i\in\mathcal{V}$ and $d\in\mathcal{Q}$,

$$f(\langle i,d\rangle)=f(\langle i+d,-1-d\rangle).$$

proof: Suppose $i \in \mathcal{V}$. Let $K_{i}$ denote the graph induced by the vertex set $Q_{i}:= i + (\mathcal Q \cup \{0\})$. Indeed, $K_{i}$ is isomorphic to $K_{5}$ as $Q_{i}$ has five elements, which are all pairwise nonconsecutive.

The cliques $K_i$ and $K_{i+2}$ intersect in the four vertices $i+\mathcal Q$, while their remaining vertices are $i$ and $i+10$. These two vertices are consecutive and hence nonadjacent. Therefore, the graph induced by $Q_i\cup Q_{i+2}$ is isomorphic to $K_4\vee\overline{K_2}$, with factors on $i+\mathcal Q$ and $\{i,i+10\}$, respectively.

By the Small overlap lemma, for every $d\in\mathcal Q$,

$$f(\{i,i+d\})=f(\{i+10,i+d\}).$$

The first edge is $\langle i,d\rangle$. To express the second edge in our chosen coordinates, note that $i+10=i-1$ and $-1-\mathcal Q=\mathcal Q$. Thus its coordinate difference from $i+d$ to $i-1$ is

$$(i-1)-(i+d)=-1-d\in\mathcal Q,$$

so $\{i+10,i+d\}=\langle i+d,-1-d\rangle$.

Naturally, we define a map $t$ called the transport map on $\mathcal{V}\times \mathcal{Q}$ by $t(i,d)=(i+d,-1-d)$. Henceforth, we will willfully blur the distinction between the transport map and its induced map on the edges of $\mathsf{A}$, writing $t(\langle i,d\rangle)=\langle i+d,-1-d\rangle$.

Thus, The big overlap lemma is equivalently stated as $tf = f$, where $f$ is a triangle free coloring of $\mathsf{A}$ and $tf$ denotes the composition of $f$ after $t$.

Theorem 1. (continued)

proof:

First, notice that $t^2(\langle i,d\rangle)=\langle i-1,d\rangle$. Thus, by induction, $t^{2n}(\langle i,d\rangle)=\langle i-n,d\rangle$. Taking $n=11$ gives $t^{22}=t^0$, so $t$ is a bijection and hence generates a cyclic group of permutations of $E(\mathsf{A})$.

Let $\langle t\rangle$ denote the cyclic group generated by $t$. We claim that

$$\operatorname{Orb}_{\langle t\rangle}(\langle0,2\rangle) =\{\langle i,d\rangle:i\in\mathcal V,\ d\in\{2,8\}\},$$ $$\operatorname{Orb}_{\langle t\rangle}(\langle0,4\rangle) =\{\langle i,d\rangle:i\in\mathcal V,\ d\in\{4,6\}\}.$$

Indeed, the identity $t^{2n}(\langle0,d\rangle)=\langle-n,d\rangle$ shows that the orbit of $\langle0,d\rangle$ contains every edge whose second coordinate is $d$. Applying $t$ to these edges shows that the same orbit contains every edge whose second coordinate is $-1-d$. On the other hand, $t$ only interchanges the second coordinates $d$ and $-1-d$. Since $-1-2=8$ and $-1-4=6$ in $\mathcal V=\mathbb Z/11\mathbb Z$, the claim follows.

By the new prescription for $\psi$, these two orbits are precisely $\psi^{-1}(R)$ and $\psi^{-1}(B)$, respectively.

Finally, since $tf=f$, every orbit of $\langle t\rangle$ is monochromatic under $f$. The two orbits must receive different colors; otherwise, every edge of $\mathsf A$ would receive the same color, contradicting the triangle-freeness of $f$. Therefore, up to exchanging the two colors, $f=\psi$.