Premium
Multipartite Ramsey numbers for odd cycles
Author(s) -
Gyárfás András,
Sárközy Gábor N.,
Schelp Richard H.
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20364
Subject(s) - combinatorics , multipartite , mathematics , conjecture , ramsey's theorem , integer (computer science) , graph , monochromatic color , extremal graph theory , discrete mathematics , line graph , voltage graph , computer science , physics , quantum mechanics , quantum entanglement , quantum , botany , biology , programming language
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