A study of two Ramsey numbers involving odd cycles
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909593347555328 |
|---|---|
| author | Gupta, Sayan |
| author_facet | Gupta, Sayan |
| contents | The \emph{book graph} of order $(n+2)$, denoted by $B_{n}$, is the graph with $n$ distinct copies of triangles sharing a common edge called the `base'. A cycle of order $m$ is denoted by $C_{m}$. A lot of studies have been done in recent years on the Ramsey number $R(B_{n}, C_{m})$. However, the exact value remains unknown for several $n$ and $m$. In 2021, Lin and Peng obtained the value of $R(B_{n}, C_{m})$ under certain conditions on $n$ and $m$. In this paper, they remarked that the value is still unknown for the range $n\in [\frac{9m}{8}-125, 4m-14]$. In a recent paper, Hu et al. determined the value of the book-cycle Ramsey number within the range $n\in [ \frac{3m-5}{2}-125, 4m]$ where $m$ is odd and $n$ is sufficiently large. In this article, we extend the investigation to smaller values of $n$. We have obtained a bound of $R(B_{n}, C_{m})$ if $n\in [2m-3, 4m-14]$ and $m\geq 7$ is odd. This is a progress on the earlier result. A connected graph $G$ is said to be \emph{$H$-good} if the formula, \begin{equation*} R(G,H)= (|G|-1)(χ(H)-1)+σ(H) \end{equation*} holds, where $χ(H)$ is the chromatic number of $H$ and $σ(H)$ is the size of the smallest colour class for the $χ(H)$-colouring. In this article, we have studied the \emph{Ramsey goodness} of the graph pair $(C_{m}, \mathbb{K}_{2,n})$, where $\mathbb{K}_{2,n}$ is the complete biparite graph. We have obtained an exact value of $R(\mathbb{K}_{2,n},C_{m})$ for all $n$ satisfying $n\geq 3493$ and $n\geq 2m+499$ where $m\geq 7$ is odd. This shows that $\mathbb{K}_{2,n}$ is $C_{m}$-good, which extends a previous result on the Ramsey goodness of $(C_{m}, \mathbb{K}_{2,n})$. Also, this improves the lower bound on $n$ from a previous result on the Ramsey number $R(B_{n}, C_{m})$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15693 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A study of two Ramsey numbers involving odd cycles Gupta, Sayan Combinatorics 05D10, 05C55, 05C35 The \emph{book graph} of order $(n+2)$, denoted by $B_{n}$, is the graph with $n$ distinct copies of triangles sharing a common edge called the `base'. A cycle of order $m$ is denoted by $C_{m}$. A lot of studies have been done in recent years on the Ramsey number $R(B_{n}, C_{m})$. However, the exact value remains unknown for several $n$ and $m$. In 2021, Lin and Peng obtained the value of $R(B_{n}, C_{m})$ under certain conditions on $n$ and $m$. In this paper, they remarked that the value is still unknown for the range $n\in [\frac{9m}{8}-125, 4m-14]$. In a recent paper, Hu et al. determined the value of the book-cycle Ramsey number within the range $n\in [ \frac{3m-5}{2}-125, 4m]$ where $m$ is odd and $n$ is sufficiently large. In this article, we extend the investigation to smaller values of $n$. We have obtained a bound of $R(B_{n}, C_{m})$ if $n\in [2m-3, 4m-14]$ and $m\geq 7$ is odd. This is a progress on the earlier result. A connected graph $G$ is said to be \emph{$H$-good} if the formula, \begin{equation*} R(G,H)= (|G|-1)(χ(H)-1)+σ(H) \end{equation*} holds, where $χ(H)$ is the chromatic number of $H$ and $σ(H)$ is the size of the smallest colour class for the $χ(H)$-colouring. In this article, we have studied the \emph{Ramsey goodness} of the graph pair $(C_{m}, \mathbb{K}_{2,n})$, where $\mathbb{K}_{2,n}$ is the complete biparite graph. We have obtained an exact value of $R(\mathbb{K}_{2,n},C_{m})$ for all $n$ satisfying $n\geq 3493$ and $n\geq 2m+499$ where $m\geq 7$ is odd. This shows that $\mathbb{K}_{2,n}$ is $C_{m}$-good, which extends a previous result on the Ramsey goodness of $(C_{m}, \mathbb{K}_{2,n})$. Also, this improves the lower bound on $n$ from a previous result on the Ramsey number $R(B_{n}, C_{m})$ |
| title | A study of two Ramsey numbers involving odd cycles |
| topic | Combinatorics 05D10, 05C55, 05C35 |
| url | https://arxiv.org/abs/2504.15693 |