﻿ 临界完全图Ramsey数
 文章快速检索
 同济大学学报(自然科学版)  2019, Vol. 47 Issue (2): 298-300.  DOI: 10.11908/j.issn.0253-374x.2019.02.020 0

### 引用本文

LI Yan, LI Yusheng. Complete Critical Ramsey Numbers[J]. Journal of Tongji University (Natural Science), 2019, 47(2): 298-300. DOI: 10.11908/j.issn.0253-374x.2019.02.020

### 文章历史

Complete Critical Ramsey Numbers
LI Yan , LI Yusheng
School of Mathematical Sciences, Tongji University, Shanghai 200092, China
Abstract: For graphs G and H, Ramsey number r(G, H) is the smallest integer r such that every 2-coloring of Kr contains either a red copy of G or a blue copy of H. Star critical Ramsey number r*(G, H) is the smallest integer n such that every 2-coloring of Kr-K1, r-1-n contains either a red copy of G or a blue copy of H. Under the inspiration of star critical Ramsey number, complete critical Ramsey number rK(G, H) is the largest integer n such that every 2-coloring of Kr-Kn contains either a red copy of G or a blue copy of H. In this paper, rK(Wn, Ka) and rK(Cn, K3) are determined. Wn=K1+Cn-1 is a wheel of size n.
Key words: Ramsey number    star critical Ramsey number    complete critical Ramsey number
1 研究背景

Hook等在文献[1-3]中确定了r*(Tn, Km)=(n-1)(m-2)+1，r*(nK2, mK2)=m, nm≥1, r*(Pn, C4)=3, n≥3和r*(Pn, Pm)=$\left\lceil {m/2} \right\rceil$nm≥4等临界星图Ramsey数.Li等在文献[4]中给出了r*(Kn, mK2)=n+2m-3, m≥1, n>2，r*(Fn, K3)=2n+2, n≥2和r*(nK4, mK3)=4n+2m, nm≥1, n≥2以及r*(nK4, mK3)=3n+3m, mn≥2.

2 主要结果的证明

 [1] HOOK J, ISAAK G. Star-critical Ramsey numbers[J]. Discrete Applied Mathematics, 2011, 159(5): 328 DOI:10.1016/j.dam.2010.11.007 [2] HOOK J. The classification of critical graphs and star-critical Ramsey numbers [D]. Bethlehem: Lehigh University, 2010. [3] HOOK J. Critical graphs for R(Pm, Pn) and the star-critical Ramsey numbers for paths[J]. Discuss Math Graph Theory, 2015, 35(4): 689 DOI:10.7151/dmgt [4] LI Z, LI Y. Some star-critical Ramsey numbers[J]. Discrete Applied Mathematics, 2015, 181(1): 301 [5] BURR S A, ERDÖS P. Generalizations of a Ramsey-theoretic result of Chvatal[J]. Journal of Graph Theory, 1983, 7(1): 39 [6] FAUDREE RJ, SCHELP RH. All Ramsey numbers for cycles in graphs[J]. Discrete Mathematics, 1974, 8(4): 313 DOI:10.1016/0012-365X(74)90151-4