EUVIMEDEUVIMED entdecken
Crossref

The $s$-chromatic Ramsey number for stars

Aijun Yi, Zhidan Luo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →