Wheel and star-critical Ramsey numbers for quadrilateral

作者：Wu Yali; Sun Yongqi^*; Radziszowski Stanislaw P

来源：Discrete Applied Mathematics, 2015, 186: 260-271.

DOI：10.1016/j.dam.2015.01.003

• Ramsey number
• Wheel
• Cycle
• Hamiltonian graph

The star-critical Ramsey number r(*)(H-1, H-2) is the smallest integer k such that every red/blue coloring of the edges of K-n - K-1,K-n-k-1 contains either a red copy of H-1 or a blue copy of H-2, where n is the graph Ramsey number R(H-1, H-2). We study the cases of r(*)(C-4, C-n) and R(C-4, W-n). In particular, we prove that r(*)(C-4, C-n) = 5 for all n >= 4, obtain a general characterization of Ramsey-critical (C-4, C-n)-graphs, and establish the exact values of R(C-4, W-n) for 9 cases of n between 18 and 44.

• 出版日期2015-5-11
• 单位北京交通大学