Ramsey numbers and Gallai--Ramsey numbers of disjoint unions of cherries
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909012708032512 |
|---|---|
| author | Zhang, Yanbo Chen, Qian Chen, Yaojun |
| author_facet | Zhang, Yanbo Chen, Qian Chen, Yaojun |
| contents | For graphs $G_1,\ldots,G_k$, the Ramsey number $R(G_1,\ldots,G_k)$ is the smallest positive integer $N$ such that every $k$-edge-coloring of $K_N$ contains a monochromatic copy of $G_i$ in color $i$ for some $i\in[k]$. The Gallai--Ramsey number $GR(G_1,\ldots,G_k)$ is defined analogously, with the colorings restricted to Gallai colorings (i.e., edge-colorings with no rainbow triangle).
A copy of $P_3$ is called a cherry. Let $n_iP_3$ denote the disjoint union of $n_i$ cherries. Wu, Magnant, Nowbandegani, and Xia (Discrete Appl. Math., 2019) proposed two conjectures: \[ R(n_1P_3,\ldots,n_kP_3)=N\ \text{and}\ GR(n_1P_3,\ldots,n_kP_3)=N\,, \] where $N=2\max\{n_1,\ldots,n_k\}+\sum_{i=1}^kn_i-k+1$. We disprove the Ramsey conjecture and provide some sufficient conditions for determining the exact value of $R(n_1P_3,\ldots,n_kP_3)$. In contrast, we confirm the Gallai--Ramsey conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02793 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Ramsey numbers and Gallai--Ramsey numbers of disjoint unions of cherries Zhang, Yanbo Chen, Qian Chen, Yaojun Combinatorics For graphs $G_1,\ldots,G_k$, the Ramsey number $R(G_1,\ldots,G_k)$ is the smallest positive integer $N$ such that every $k$-edge-coloring of $K_N$ contains a monochromatic copy of $G_i$ in color $i$ for some $i\in[k]$. The Gallai--Ramsey number $GR(G_1,\ldots,G_k)$ is defined analogously, with the colorings restricted to Gallai colorings (i.e., edge-colorings with no rainbow triangle). A copy of $P_3$ is called a cherry. Let $n_iP_3$ denote the disjoint union of $n_i$ cherries. Wu, Magnant, Nowbandegani, and Xia (Discrete Appl. Math., 2019) proposed two conjectures: \[ R(n_1P_3,\ldots,n_kP_3)=N\ \text{and}\ GR(n_1P_3,\ldots,n_kP_3)=N\,, \] where $N=2\max\{n_1,\ldots,n_k\}+\sum_{i=1}^kn_i-k+1$. We disprove the Ramsey conjecture and provide some sufficient conditions for determining the exact value of $R(n_1P_3,\ldots,n_kP_3)$. In contrast, we confirm the Gallai--Ramsey conjecture. |
| title | Ramsey numbers and Gallai--Ramsey numbers of disjoint unions of cherries |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.02793 |