On the 3-Color Ramsey Numbers R(C4, C4, Wn)

Xuemei Zhang; Yaojun Chen; T. C.Edwin Cheng

doi:10.1007/s00373-022-02505-y

On the 3-Color Ramsey Numbers R(C₄, C₄, W_n)

Xuemei Zhang
, Yaojun Chen
, T. C.Edwin Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

Abstract

For given graphs G₁, G₂, ⋯ , G_k, k≥ 2 , the k-color Ramsey number, denoted by R(G₁, G₂, … , G_k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of G_i in color i, for some 1 ≤ i≤ k. Let C_m be a cycle of length m and W_n a wheel of order n+ 1. In this paper, we show that R(C4,C4,Wn)≤n+⌈4n+5⌉+3 for n= 42 , 48 , 49 , 50 , 51 , 52 or n≥ 56. Furthermore, we prove that R(C4,C4,Wℓ2-ℓ)≤ℓ2+ℓ+2 for ℓ≥ 9 , and if ℓ is a prime power, then the equality holds.

Original language	English
Article number	103
Journal	Graphs and Combinatorics
Volume	38
Issue number	3
DOIs	https://doi.org/10.1007/s00373-022-02505-y
Publication status	Published - Jun 2022

Keywords

Multicolor Ramsey number
Quadrilateral
Wheel

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

More information

10.1007/s00373-022-02505-y

Cite this

@article{f4ffb35f2aec407984e26c6753547869,

title = "On the 3-Color Ramsey Numbers R(C4, C4, Wn)",

abstract = "For given graphs G1, G2, ⋯ , Gk, k≥ 2 , the k-color Ramsey number, denoted by R(G1, G2, … , Gk) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of Gi in color i, for some 1 ≤ i≤ k. Let Cm be a cycle of length m and Wn a wheel of order n+ 1. In this paper, we show that R(C4,C4,Wn)≤n+⌈4n+5⌉+3 for n= 42 , 48 , 49 , 50 , 51 , 52 or n≥ 56. Furthermore, we prove that R(C4,C4,Wℓ2-ℓ)≤ℓ2+ℓ+2 for ℓ≥ 9 , and if ℓ is a prime power, then the equality holds.",

keywords = "Multicolor Ramsey number, Quadrilateral, Wheel",

author = "Xuemei Zhang and Yaojun Chen and Cheng, \{T. C.Edwin\}",

note = "Funding Information: Zhang was supported by NSFC under grant number 11801520 and ZJNSF under grant number LY18A010014, and Chen was supported by NSFC under Grant numbers 11671198, 11871270 and 12161141003. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.",

year = "2022",

month = jun,

doi = "10.1007/s00373-022-02505-y",

language = "English",

volume = "38",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - On the 3-Color Ramsey Numbers R(C4, C4, Wn)

AU - Zhang, Xuemei

AU - Chen, Yaojun

AU - Cheng, T. C.Edwin

N1 - Funding Information: Zhang was supported by NSFC under grant number 11801520 and ZJNSF under grant number LY18A010014, and Chen was supported by NSFC under Grant numbers 11671198, 11871270 and 12161141003. Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.

PY - 2022/6

Y1 - 2022/6

N2 - For given graphs G1, G2, ⋯ , Gk, k≥ 2 , the k-color Ramsey number, denoted by R(G1, G2, … , Gk) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of Gi in color i, for some 1 ≤ i≤ k. Let Cm be a cycle of length m and Wn a wheel of order n+ 1. In this paper, we show that R(C4,C4,Wn)≤n+⌈4n+5⌉+3 for n= 42 , 48 , 49 , 50 , 51 , 52 or n≥ 56. Furthermore, we prove that R(C4,C4,Wℓ2-ℓ)≤ℓ2+ℓ+2 for ℓ≥ 9 , and if ℓ is a prime power, then the equality holds.

AB - For given graphs G1, G2, ⋯ , Gk, k≥ 2 , the k-color Ramsey number, denoted by R(G1, G2, … , Gk) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of Gi in color i, for some 1 ≤ i≤ k. Let Cm be a cycle of length m and Wn a wheel of order n+ 1. In this paper, we show that R(C4,C4,Wn)≤n+⌈4n+5⌉+3 for n= 42 , 48 , 49 , 50 , 51 , 52 or n≥ 56. Furthermore, we prove that R(C4,C4,Wℓ2-ℓ)≤ℓ2+ℓ+2 for ℓ≥ 9 , and if ℓ is a prime power, then the equality holds.

KW - Multicolor Ramsey number

KW - Quadrilateral

KW - Wheel

UR - https://www.scopus.com/pages/publications/85130774606

U2 - 10.1007/s00373-022-02505-y

DO - 10.1007/s00373-022-02505-y

M3 - Journal article

AN - SCOPUS:85130774606

SN - 0911-0119

VL - 38

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

M1 - 103

ER -