Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The $s$-chromatic Ra ...
Article

The $s$-chromatic Ramsey number for stars

Aijun Yi ORCID (1), Zhidan Luo ORCID (1)
(1) Hainan University
Download article
Open on arXiv
Submitted on
December 19, 2025
Accepted on
July 20, 2026
Published on
August 21, 2026
Last modified on
August 21, 2026
Volume 28
vol. 28:3
Graph Theory
DOI
10.46298/dmtcs.17152
License
arXiv.org - Non-exclusive license to distribute
Indicators
100
Views
50
Downloads

The $s$-chromatic Ramsey number for stars

Aijun Yi ORCID (1), Zhidan Luo ORCID (1)
(1) Hainan University
Abstract
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}})$.
Keywords
  • Combinatorics
Preview
Loading PDF preview...
References
  1. B. Bollobás. Extremal Graph Theory. Reprint of the 1978 original, Dover Publications, 2004.

  2. M. Budden. Star-critical Ramsey numbers for graphs. Springer Cham, 2023.

    DOI : 10.1007/978-3-031-29981-0
  3. M. Budden and E. DeJonge. Multicolor star-critical Ramsey numbers and Ramsey-good graphs. Electron. J. Graph Theory Appl., 10(1):51-66, 2022.

    DOI : 10.5614/ejgta.2022.10.1.4
  4. M. Budden, M. Moun, and J. Jakhar. Star-critical weakened Ramsey numbers. Theory and Appl. of Graphs, 12(2):#4, 2025.

    DOI : 10.20429/tag.2025.120204
  5. S. Burr and J. Roberts. On Ramsey numbers for stars. Util. Math., 4:217-220, 1973.

  6. K. Chung and C. Liu. A generalization of Ramsey theory for graphs. Discrete Math., 21(2):117-127, 1978.

    DOI : 10.1016/0012-365x(78)90084-5
  7. K. Chung, M. Chung, and C. Liu. A generalization of Ramsey theory for graphs - with stars and complete graphs as forbidden graphs. Conger. Numer., 19:155-161, 1997.

  8. F. Harary. Graph Theory. Addison-Wesley, 1969.

  9. F. Harary. Recent results on generalized Ramsey theory for graphs. In Y. Alavi, D. R. Lick, and A. T. White, editors, Graph Theory and Applications, pages 125-138, 1972.

    DOI : 10.1007/bfb0067364
  10. H. Harborth and M. Möller. Weakened Ramsey numbers. Discrete Appl. Math., 95(1-3):279-284, 1999.

    DOI : 10.1016/s0166-218x(99)00081-5
  11. J. Hook. The classification of critical graphs and star-critical Ramsey numbers. Phd thesis, Lehigh University, 2010.

  12. J. Hook. Recent developments of star-critical Ramsey numbers. In F. Hoffman, S. Holliday, Z. Rosen, F. Shahrokhi, and J. Wierman, editors, Combinatorics, Graph Theory, and Computing, pages 245-254, 2024.

    DOI : 10.1007/978-3-031-52969-6_22
  13. A. Khamseh and G. Omidi. A generalization of Ramsey theory for stars and one matching. Math. Reports, 69(1):85-92, 2017.

  14. A. Khamseh and G. Omidi. Large stars with few colors. Math. Reports, 24(74):363-375, 2022.

  15. Z. Luo. A generalization of Ramsey theory for stars and one matching. Discuss. Math. Graph Theory, 45 (2):755-762, 2025.

    DOI : 10.7151/dmgt.2550
  16. S. Radziszowski. Small Ramsey numbers. Electron. J. Combin., DS1.17:133 pp, 2024.

    DOI : 10.37236/21
  17. F. Ramsey. On a problem of formal logic. Proc. Lond. Math. Soc., s2-30(1):264-286, 1930.

    DOI : 10.1112/plms/s2-30.1.264