Journal of Combinatorics

Volume 8 (2017)

Number 1

Circular chromatic Ramsey number

Pages: 189 – 208

DOI: http://dx.doi.org/10.4310/JOC.2017.v8.n1.a7

Authors

Kyle F. Jao (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Claude Tardif (Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, Ontario, Canada)

Douglas B. West (Department of Mathematics, Zhejiang Normal University, Jinhua, China; and Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Xuding Zhu (Department of Mathematics, Zhejiang Normal University, Jinhua, China)

Abstract

Let $\chi_c (H)$ denote the circular chromatic number of a graph $H$. For graphs $F$ and $G$, the circular chromatic Ramsey number $R_{\chi_c} (F,G)$ is the infimum of $\chi_c (H)$ over graphs $H$ such that every red/blue edge-coloring of $H$ contains a red copy of $F$ or a blue copy of $G$. We characterize $R_{\chi_c} (F,G)$ in terms of a Ramsey problem for the families of homomorphic images of $F$ and $G$. Letting $z_t = 3-2^{-t}$, we prove that $z_{t-1} \lt \chi_c (G) \leq z_t$ implies $2_{z_{t-1}} \leq R_{\chi_c} (G,G) \leq 2_{z_t}$. For integer $k$ with $k \gt 1$, there is a graph $G$ with $\chi_c (G) \geq k$ and $R_{\chi_c} (G,G) \leq k (k-1)$. Our most difficult result is $R_{\chi_c} (F,G) = 4$ when $\chi_c (F) , \chi_c (G) \in (2, \frac{5}{2}]$. As a consequence, no graph $G$ satisfies $4 \lt R_{\chi_c} (G,G) \lt 5$. We also prove $\frac{14}{3} \leq R_{\chi_c} (C_3, C_5) \leq 5$ and $4 \leq R_{\chi_c} (C_3, C_7) \leq \frac{9}{2}$.

Keywords

Ramsey theory, circular chromatic number, parameter Ramsey number, homomorphism, categorical product

2010 Mathematics Subject Classification

Primary 05C55. Secondary 05C15.

Full Text (PDF format)

Published 2 December 2016