KIT | KIT-Bibliothek | Impressum | Datenschutz

Chromatic Ramsey Numbers and Two‐Color Turán Densities

Axenovich, Maria 1; Gaa, Simon 1; Liu, Dingyuan 1
1 Fakultät für Mathematik (MATH), Karlsruher Institut für Technologie (KIT)

Abstract:

Given a graph $G$, its 2‐color Turán numbern e$_x$$^{(2)}$ (n, $G$) is the maximum number of edges in an $n$‐vertex graph, suchthat the edges can be colored with two colors avoiding a monochromatic copy of $G$. Let $\pi^{(2)}$ ($G$) = lim$_{n -> \infty}$ ex$^{(2)}$ $(n, $G$)$ / ($\frac{n}{2}$) be the 2‐color Turán density of $G$. What real numbers in the interval (0,1) are realized as the 2‐color Turán density of some graph? It is known that $\pi^{(2)}$ ($G$) = 1 - (R$_x$ ($G$) - 1)$^{-1}$, where R$_x$ ($G$) is the chromatic Ramsey number of $G$. Burr, Erdős, and Lovász showed that (k - 1)$^2$ + 1 $\leq$ $R_x$ ($G$) $\leq$ $R$ (k), for any k‐chromatic graph $G$, where $R$ (k) is the classical Ramsey number. However, it is an open problem to determine how manydistinct values between (k - 1)$^2$ + 1 and $R$ (k) can be realized as $R$$_x$ ($G$) of some k‐chromatic graph $G$ for general k. In this paper, among others, we prove that there are $\Omega$(k) different values of $R_x$ ($G$) among k‐chromatic graphs $G$. This sheds more light on the possible 2‐color Turán densities of graphs.


Verlagsausgabe §
DOI: 10.5445/IR/1000194843
Veröffentlicht am 30.06.2026
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Mathematik (MATH)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2026
Sprache Englisch
Identifikator ISSN: 0364-9024, 1097-0118
KITopen-ID: 1000194843
Erschienen in Journal of Graph Theory
Verlag John Wiley and Sons
Vorab online veröffentlicht am 21.06.2026
Nachgewiesen in OpenAlex
Scopus
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page