On three color Ramsey numbers [Formula presented]

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

For [Formula presented] given graphs [Formula presented], [Formula presented], the [Formula presented]-color Ramsey number, denoted by [Formula presented], is the smallest integer [Formula presented] such that if we arbitrarily color the edges of a complete graph of order [Formula presented] with [Formula presented] colors, then it always contains a monochromatic copy of [Formula presented] colored with [Formula presented], for some [Formula presented]. Let [Formula presented] be a cycle of length [Formula presented] and [Formula presented] a star of order [Formula presented]. In this paper, firstly we give a general upper bound of [Formula presented]. In particular, for the 3-color case, we have [Formula presented] and this bound is tight in some sense. Furthermore, we prove that [Formula presented] for all [Formula presented] and [Formula presented], and if [Formula presented] is a prime power, then the equality holds.

Original languageEnglish
Pages (from-to)285-291
Number of pages7
JournalDiscrete Mathematics
Volume342
Issue number2
DOIs
Publication statusPublished - Feb 2019

Keywords

  • Multicolor Ramsey number
  • Polarity graph
  • Quadrilateral
  • Singer difference set
  • Star

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this