✦ LIBER ✦

Multipartite Ramsey numbers for odd cycles

✍ Scribed by András Gyárfás; Gábor N. Sárközy; Richard H. Schelp

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 119 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20364

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K((n−1)/2, (n−1)/2, (n−1)/2, (n−1)/2, 1) there is a monochromatic C~n~, a cycle of length n. This roughly says that the Ramsey number for C~n~ (i.e. 2__n__−1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K~2__n__−1~ the edges within a set of size (n+ 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009

📜 SIMILAR VOLUMES

The multi-color Ramsey number of an odd

The multi-color Ramsey number of an odd cycle

✍ Yusheng Li 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

## Abstract Let __r__~__k__~(__G__) be the __k__‐color Ramsey number of a graph __G__. It is shown that $r\_{k}(C\_{5})\le \sqrt{18^{k}\,k!}$ for __k__⩾2 and that __r__~__k__~(__C__~2__m__+ 1~)⩽(__c__^__k__^__k__!)^1/__m__^ if the Ramsey graphs of __r__~__k__~(__C__~2__m__+ 1~) are not far away fr

Bipartite anti-Ramsey numbers of cycles

✍ Maria Axenovich; Tao Jiang; André Kündgen 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB

## Abstract We determine the maximum number of colors in a coloring of the edges of __K~m,n~__ such that every cycle of length 2__k__ contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers __q__

The chromatic Ramsey number of odd wheel

The chromatic Ramsey number of odd wheels

✍ Nathalie Paul; Claude Tardif 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

We prove that the chromatic Ramsey number of every odd wheel W 2k+1 , k ≥ 2 is 14. That is, for every odd wheel W 2k+1 , there exists a 14-chromatic graph F such that when the edges of F are two-coloured, there is a monochromatic copy of W 2k+1 in F, and no graph F with chromatic number 13 has the s

On the multi-colored Ramsey numbers of c

On the multi-colored Ramsey numbers of cycles

✍ Tomasz Łuczak; Miklós Simonovits; Jozef Skokan 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB

For a graph L and an integer k ≥ 2, R k (L) denotes the smallest integer N for which for any edge-coloring of the complete graph K N by k colors there exists a color i for which the corresponding color class contains L as a subgraph.

Ramsey Numbers for Matroids

✍ Talmage James Reid 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 233 KB

Tripartite Ramsey numbers for paths

✍ András Gyárfás; Miklós Ruszinkó; Gábor N. Sárközy; Endre Szemerédi 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph __K__(__n__, __n__, __n__) there is a monochromatic path of length (1 − __o__(1))2__n__. Since __R__(__P__~2__n__+1~,__P__~2__n__+1~)=3__n__,