Ramsey Number of Wheels Versus Cycles and Trees

Raeisi, Ghaffar ; Zaghian, Ali

Canadian mathematical bulletin, Tome 59 (2016) no. 1, pp. 190-196

Résumé

Let ${{G}_{1}},\,{{G}_{2}},\,.\,.\,.\,,\,{{G}_{t}}$ be arbitrary graphs. The Ramsey number $R\left( {{G}_{1}},\,{{G}_{2}},\,.\,.\,.,{{G}_{t}} \right)$ is the smallest positive integer $n$ such that if the edges of the complete graph ${{K}_{n}}$ are partitioned into $t$ disjoint color classes giving $t$ graphs ${{H}_{1}},\,{{H}_{2}},\,.\,.\,.\,,\,{{H}_{t}}$ , then at least one ${{H}_{i}}$ has a subgraph isomorphic to ${{G}_{i}}$ . In this paper, we provide the exact value of the $R({{T}_{n}},\,{{W}_{m}})$ for odd $m,\,n\,\ge \,m-1$ , where ${{T}_{n}}$ is either a caterpillar, a tree with diameter at most four, or a tree with a vertex adjacent to at least $\left\lceil \frac{n}{2} \right\rceil \,-\,2$ leaves, and ${{W}_{n}}$ is the wheel on $n\,+\,1$ vertices. Also, we determine $R\left( {{C}_{n}},\,{{W}_{m}} \right)$ for even integers $n$ and $m,\,n\,\ge \,m\,+\,500$ , which improves a result of Shi and confirms a conjecture of Surahmat et al. In addition, the multicolor Ramsey number of trees versus an odd wheel is discussed in this paper.

Détail

DOI : 10.4153/CMB-2015-057-5

Mots-clés : 05C15, 05C55, 05C65, Ramsey number, wheel, tree, cycle