The k-Ramsey number for cycles

Abstract

Let 𝐹 and 𝐻 be two graphs. The Ramsey number 𝑅(𝐹, 𝐻) is defined as the smallest positive integer 𝑛 such that for any red-blue coloring of the edges of 𝐾𝑛 there is a subgraph of 𝐾𝑛 isomorphic to 𝐹 whose edges are all colored red, or a subgraph of 𝐾𝑛 isomorphic to 𝐻 whose edges are all colored blue.

Let 𝐹 and 𝐻 now be two bipartite graphs with Ramsey number 𝑅(𝐹, 𝐻). Further, let 𝐺 be a complete 𝑘-partite graph 𝐾𝑛1,𝑛2,...,𝑛𝑘 of order 𝑛 = ∑ 𝑛𝑖 𝑘 𝑖=1 with 𝑛𝑖 ∈ {⌈𝑛 𝑘⁄ ⌉, ⌊𝑛 𝑘⁄ ⌋} for 𝑖 = 1, ... , 𝑘 and 𝑘 = 2, ... , 𝑅(𝐹, 𝐻). The 𝑘-Ramsey number 𝑅𝑘(𝐹, 𝐻) is then defined as the smallest positive integer 𝑛 such that for any red- blue coloring of the edges of 𝐺 there is a subgraph of 𝐺 isomorphic to 𝐹 whose edges are all colored red, or a subgraph of 𝐺 isomorphic to 𝐻 whose edges are all colored blue. The 𝑘-Ramsey number 𝑅𝑘(𝐹, 𝐻) is defined in [2] for two bipartite graphs 𝐹 and 𝐻 only.

In the thesis we investigate the 𝑘-Ramsey number of two cycles which are not both bipartite. Amongst other results, we determine 𝑅𝑘(𝐶3, 𝐶4), 𝑅𝑘(𝐶3, 𝐶5), 𝑅𝑘(𝐶4, 𝐶5) and 𝑅𝑘(𝐶5, 𝐶5) for all the possible values of 𝑘 in each case. From these results and others, we conclude with a conjecture regarding the formula for 𝑅𝑘(𝐶2𝑛+1, 𝐶2𝑚+1) where 𝑛 ≥ 𝑚 ≥ 1, (𝑛, 𝑚) ≠ (1,1) and 𝑘 = 5, ... ,4𝑛 + 1.

We show that 𝑅2(𝐹, 𝐻) does not exist when 𝐹 is nonbipartite and 𝐻 is a nonempty graph. We also show that 𝑅𝑘(𝐾𝑛, 𝐻) does not exist when 𝐻 is a nonempty graph and 2 ≤ 𝑘 < 𝑛.