临界完全图Ramsey数
|
摘要
设G和H是任意的图,Ramsey数r(G,H)定义为最小的正整数r,使得图K_r的任意红蓝二边着色或存在单色的红色子图G,或存在单色的蓝色子图H.临界星图Ramsey数r_*(G,H)为最小的正整数n,使得图K_r-K_(1,r-1-n)的任意红蓝二边着色或存在单色的红色子图G,或存在单色的蓝色子图H.在临界星图启发下,临界完全图Ramsey数r_K(G,H)定义为最大的正整数n,使得图K_r-K_n的任意红蓝二边着色或存在单色的红色子图G或存在单色的蓝色子图H.这里r为Ramsey数r(G,H).确定了r_K(W_(1,n),K_3)和r_K(C_n,K_3),其中W_(1,n)=K_1+C_n为轮.
For graphs G and H, Ramsey number r(G,H) is the smallest integer r such that every 2-coloring of K_r 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 K_r-K_(1,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 r_K(G,H) is the largest integer n such that every 2-coloring of K_r-K_n contains either a red copy of G or a blue copy of H. In this paper, r_K(W_n,K_a) and r_K(C_n,K_3) are determined. W_n=K_1+C_(n-1) is a wheel of size n.
For graphs G and H, Ramsey number r(G,H) is the smallest integer r such that every 2-coloring of K_r 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 K_r-K_(1,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 r_K(G,H) is the largest integer n such that every 2-coloring of K_r-K_n contains either a red copy of G or a blue copy of H. In this paper, r_K(W_n,K_a) and r_K(C_n,K_3) are determined. W_n=K_1+C_(n-1) is a wheel of size n.
引文
[1] HOOK J, ISAAK G. Star-critical Ramsey numbers [J]. Discrete Applied Mathematics, 2011,159(5):328.
[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.
[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.
[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.
[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.