The $s$-chromatic Ramsey number for stars
Discrete Mathematics & Theoretical Computer Science · 21.08.2026 · vol. 28:3 (Graph Theory)
DOI: 10.46298/dmtcs.17152 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 21.08.2026. Verfasst von Aijun Yi und 1 weiteren Autor:innen.
Abstract (Originalsprache)
In 1977, Chung, Chung and Liu generalized the definition of the Ramsey number. They introduced the $s$-chromatic Ramsey number as follows. Let $1\leq s< t$ be integers and let $A_{1}, A_{2}, \dots, A_{c}$ be subsets with size $s$ of $[t]$, where $c= {t\choose s}$. For given graphs $G_{1}, G_{2}, \dots, G_{c}$, the {\it $s$-chromatic Ramsey number} $r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum positive integer $N$ such that every $t$-coloring of $E(K_{N})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$. The {\it star-critical $s$-chromatic Ramsey number} $r_{*}^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum integer $\ell$ such that every $t$-coloring of the edges in $K_{N}- E(K_{1, N- 1- \ell})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$, where $N= r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$. If $G_{1}= G_{2}= \dots= G_{c}= G$, then we simplify them to $r^{s, t}(G)$ (also called the {\it weakened Ramsey number}) and $r^{s, t}_{*}(G)$, respectively. In this paper, we determine all the values of $r^{s, t}(K_{1, m})$ and $r_{*}^{s, t}(K_{1, m})$, and part of the value of $r^{s, t}(K_{1, m_{1}}, K_{1, m_{2}}, \dots, K_{1, m_{c}})$.
Zitieren
APA
Yi, A., & Luo, Z. (2026). The $s$-chromatic Ramsey number for stars. Discrete Mathematics & Theoretical Computer Science, vol. 28:3(Graph Theory). https://doi.org/10.46298/dmtcs.17152
Vancouver
Yi A, Luo Z. The $s$-chromatic Ramsey number for stars. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:3(Graph Theory). doi:10.46298/dmtcs.17152
BibTeX
@article{Yi2026,
author = {Yi, Aijun and Luo, Zhidan},
title = {The $s$-chromatic Ramsey number for stars},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:3},
number = {Graph Theory},
doi = {10.46298/dmtcs.17152}
}
EUVIMED