On the Multi-coloured Ramsey Numbers of Cycles

Details On the Multi-coloured Ramsey Numbers of Cycles On the Multi-coloured Ramsey Numbers of Cycles

2010-05-21

arxiv.org/abs/1005.3926v2

Mathematics

Combinatorics

8 pages, 0 figures Added references. Corrected typos

Scientific paper

For a graph $L$ and an integer $k\geq 2$, $R_k(L)$ denotes the smallest integer $N$ for which for any edge-colouring of the complete graph $K_N$ by $k$ colours there exists a colour $i$ for which the corresponding colour class contains $L$ as a subgraph. Bondy and Erd\H{o}s conjectured that for an odd cycle $C_n$ on $n$ vertices, $$R_k(C_n) = 2^{k-1}(n-1)+1 \text{for $n>3$.}$$ They proved the case when $k=2$ and also provided an upper bound $R_k(C_n)\leq (k+2)!n$. Recently, this conjecture has been verified for $k=3$ if $n$ is large. In this note, we prove that for every integer $k\geq 4$, $$R_k(C_n)\leq k2^kn+o(n), \text{as $n\to\infty$.}$$ When $n$ is even, Yongqi, Yuansheng, Feng, and Bingxi gave a construction, showing that $R_k(C_n)\geq (k-1)n-2k+4.$ Here we prove that if $n$ is even, then $$R_k(C_n)\leq kn+o(n), \text{as $n\to\infty$.}$$

Affiliated with

Also associated with

No associations

Rating

On the Multi-coloured Ramsey Numbers of Cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Multi-coloured Ramsey Numbers of Cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Multi-coloured Ramsey Numbers of Cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-339541