Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Abstract view

Ramsey Number of Wheels Versus Cycles and Trees

 Printed: Mar 2016
  • Ghaffar Raeisi,
    Department of Mathematical Sciences, Shahrekord University, Shahrekord, P.O. Box 115, Iran
  • Ali Zaghian,
    Department of Mathematics and Cryptography, Malek-Ashtar University of Technology, Isfahan, P.O. Box 83145/115, Iran
Format:   LaTeX   MathJax   PDF  


Let $G_1, G_2, \dots , G_t$ be arbitrary graphs. The Ramsey number $R(G_1, G_2, \dots, G_t)$ 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,\dots,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\geq 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 $\lceil \frac{n}{2}\rceil-2$ leaves. Also, we determine $R(C_n,W_m)$ for even integers $n$ and $m$, $n\geq 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.
Keywords: Ramsey number, wheel, tree, cycle Ramsey number, wheel, tree, cycle
MSC Classifications: 05C15, 05C55, 05C65 show english descriptions Coloring of graphs and hypergraphs
Generalized Ramsey theory [See also 05D10]
05C15 - Coloring of graphs and hypergraphs
05C55 - Generalized Ramsey theory [See also 05D10]
05C65 - Hypergraphs

© Canadian Mathematical Society, 2018 :