Circular chromatic Ramsey number

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