1 研究背景

文中研究的图均为简单图.设G和H是任意的两个图.Ramsey数r(G, H)定义为最小的正整数r，使得图K_r的任意红蓝二边着色或存在单色的红色子图G，或存在单色的蓝色子图H.实际上，在Ramsey数的研究中，并不需要完全图的所有边即可找到单色的红色子图G或单色的蓝色子图H.因此，Hook等^[1]首先在文献[1]中提出临界星图Ramsey数r_*(G, H)并确定了一些临界星图Ramsey数.下面给出临界星图Ramsey数的定义.

定义1  设r=r(G, H)为Ramsey数，临界星图Ramsey数r_*(G, H)定义为最小的正整数n，使得图K_r-K_{1, r-1-n}的任意红蓝二边着色或存在单色的红色子图G，或存在单色的蓝色子图H.

Hook等在文献[1-3]中确定了r_*(T_n, K_m)=(n-1)(m-2)+1，r_*(nK₂, mK₂)=m, n≥m≥1, r_*(P_n, C₄)=3, n≥3和r_*(P_n, P_m)=$\left\lceil {m/2} \right\rceil $，n≥m≥4等临界星图Ramsey数.Li等在文献[4]中给出了r_*(K_n, mK₂)=n+2m-3, m≥1, n>2，r_*(F_n, K₃)=2n+2, n≥2和r_*(nK₄, mK₃)=4n+2m, n≥m≥1, n≥2以及r_*(nK₄, mK₃)=3n+3m, m≥n≥2.

临界星图Ramsey数是在完全图中删掉最大星图的导出子图中寻找单色红色子图G或单色蓝色子图H.进一步发现，在寻找Ramsey数的过程中，完全图K_r的边可以在删掉星图后继续减少，仍然可能存在单色红色子图G或单色蓝色子图H.

定义2  设r=r(G, H)为Ramsey数，临界完全图Ramsey数为最大的正整数n，使得图K_r-K_n的任意红蓝二边着色或存在单色的红色子图G或存在单色的蓝色子图H.

文中，G+H表示通过G和H之间完全连边所得到的图.如果V(H)⊆V(G)，G∨H表示把H中不属于E(G)的边添加到G中所得到的图.如果H是G的子图，G-H表示从图G中删掉H的边所得到的图.G\H表示从图G中删掉图H的点和边所得到的图.N_G^R(v)和d_G^R(v)分别为顶点v在图G中的红邻域和红度，同理N_G^B(v)和d_G^B(v)分别为G中顶点v的蓝邻域和蓝度.

定理1  当整数n≥5时，r_K(W_{1, n}, K₃)=$\left\lfloor {n/2} \right\rfloor $.

定理2  当整数n≥4时，r_K(C_n, K₃)=$\left\lfloor {n/2} \right\rfloor $.

2 主要结果的证明

引理1^[5]  当整数n≥5，r(W_{1, n}, K₃)=2n+1.

引理2^[6]  当整数n≥4，r(C_n, K₃)=2n-1.

引理3^[2]  当整数n≥3，r_*(C_n, K₃)=n+1.当整数n≥5，r_*(W_{1, n}, K₃)=n+3.

定理1的证明.因为n为奇数时证明与偶数类似，所以本文只证明偶数情况.首先证明r_K(W_{1, n}, K₃)≤$\left\lfloor {n/2} \right\rfloor $.考虑图$\mathit{G = }{\mathit{K}_{2n + 1}} - {K_{\frac{n}{2} + 1}} $，即${K_{\frac{{3n}}{2}}} \vee \left( {n/2 + 1} \right){K_1} $.令${G_1} = {K_{n, \frac{n}{2}}} $为蓝色二部图，其点集为V(G₁)=C₁∪C₂, C_i, i=1, 2为红色团.G₂=(n/2+1)K₁与C₁连蓝边，与C₂连红边.显然图G不存在红色的W_{1, n}与蓝色的K₃.所以r_K(W_{1, n}, K₃)≤$\left\lfloor {n/2} \right\rfloor $.

只需证明r_K(W_{1, n}, K₃)≥$\left\lfloor {n/2} \right\rfloor $.证明采用归纳假设法，当n=5，r(W_{1, 5}, K₃)=11，r_*(W_{1, 5}, K₃)=8，则r_K(W_{1, 5}, K₃)=2.假设当n≥6时，r_K(W_{1, n-1}, K₃)=$\left\lfloor {n - 1/2} \right\rfloor $.考虑图$G = {K_{2n + 1}} - {K_{\frac{n}{2}}} $，即${K_{\frac{{3n}}{2} + 1}} \vee n/2{K_1} $.反证假设G中不存在红色W_{1, n}和蓝色K₃.根据归纳假设G存在红色W_{1, n-1}.设W_{1, n-1}中的中心点为v，R_v为点v在G\W_{1, n-1}的红邻域，B_v为点v在G\W_{1, n-1}的蓝邻域, 圈为C_n-1=a₁a₂…a_n-1.令${G_1} = {K_{\frac{{3n}}{2} + 1}} $，${G_2} = \frac{n}{2}{K_1} $, A={a_i|a_i+1∈G₁}, A₁={a_i|a_i∈G₁, a_i+1∈G₁}，B={a_i|a_i+1∈G₂}.可知|A|≥n/2，|A₁|≥1，不妨设a_n-1∈A₁，v∈G₁，则a_n-1a₁∈G₁.若v∈G₂，C_n-1∈G₁，v的任意红邻居至多可与C_n-1连一条红边，因此C_n-1至少存在红色K_n-2，可以找到一个新轮满足v∈G₁.

情形1  |A₁|≥2.因不存在蓝色K₃，B_v中不存在蓝边.R_v中亦无蓝边，若不然，存在蓝边u₁u₂，u₁∈G₁, u₂∈G₁时，v的任意红邻居至多可与A连一条红边，此时C_n-1中存在一点与u₁u₂都连蓝边形成蓝色K₃，与假设矛盾.u₁∈G₁, u₂∈G₂时，d_A^R(u₁)≤1, d_A1^R(u₂)≤1且d_A^R(u₁)=1时d_B^R(u₁)=0.d_A^R(u₁)=1，d_A1^R(u₂)=1或者d_A^R(u₁)=0，d_A1^R(u₂)=0时，C_n-1∩G₁中一定存在一点与u₁u₂都连蓝边，形成蓝色K₃.d_A^R(u₁)=1，d_A1^R(u₂)=0或d_A^R(u₁)=0，d_A1^R(u₂)=1，因为|A₁|≥2所以A₁中存在一点与u₁u₂都连蓝边，形成蓝色K₃.

R_v∩G₁的点与B_v全连红边，若不然，存在蓝边uw，u∈R_v∩G₁，w∈B_v.d_A^R(u)≤1，如果d_A^R(u)=1，设ua_i，a_i∈A为红边，则d_C^B(u)=n-2，即C_n-1\{a_i}中无蓝边，w与(C_n-1\{a_i})∩G₁连红边，此时可找到以a_i+1为中心点的新的轮W_{1, n}，矛盾.如果d_A^R(u)=0且d_B^R(u)=0，W_{1, n-1}中无蓝边，w与C_n-1∩G₁全连红边，形成红色W_{1, n}.若d_B^R(u)=1，设ua_j, a_j∈B为红边，d_Cn-1^B(u)=n-2，则C_n-1\{a_j}中不存在蓝边且w与(C_n-1\{a_j})∩G₁全连红边.此时若d_Cn-1^R∩G₁(a_j)≥1，即可找到以N_Cn-1^R∩G₁(a_j)任意一点为中心点的红色W_{1, n}；d_Cn-1^R∩G₁(a_j)=0时，则a_j与C_n-1∩G₁全连蓝边，设K_2n+1\({w}∪W_{1, n-1})为H, 若d_H^B(a_j)≥1或d_H^B(u)≥1则可找到红色W_{1, n}.因此K_2n+1\({w}∪W_{1, n-1})为点a_j和u的公共红邻域.检查N_H^R(v)可发现，N_H^R(v)中任意一点与a_j必连红边，否则会产生以C_n-1∩G₁任意一点为中心点的红色W_{1, n}，与C_n-1∩G₁必连蓝边，否则会产生以v为中心点的红色W_{1, n}，并且N_H^R(v)中任意一点x满足d_H^B(x)=0，否则会产生以C_n-1∩G₁任意一点为中心点的红色W_{1, n}.至此可发现在H中，N_H^R(v)与N_H^B(v)全连红边，产生红色W_{1, n}，矛盾.若d_B^R(u)≥2，设ua_k, ua_l, a_k, a_l∈B, k < l为红边，k=1.若k≠1，即ua₁为蓝色，a_k, a_l∈B，a_k+1, a_l+1∈A，且因为假设a_n-1∈A, ua_l+1为蓝色，a₁a_l+1为红色，则a₁a_kua_la_k+1a_n-1a_n-2a_l+1a₁与点v构成红色W_{1, n}，矛盾.此时改变圈C_n-1的下标，从a_i变为a_n-i，得到a_k∈A，d_A^R(u)=1，证明与上述相同.

设R_v∩G₂点为u₁u₂…u_p.若R_v∩G₂的点与B_v全连红边，形成红色W_{1, n}.假设存在一点u_i∈R_v∩G₂，w∈B_v，w∈G₁，u_iw为蓝边.d_A1^R(u_i)≤1.若d_A1^R(u_i)=1，设u_ia_i为红边，a_i∈A₁，则u_i与(C_n-1\{a_i})∩G₁即B∪A₁全连蓝边，为不产生蓝色K₃，w与B∪A₁全连红边.注意到若(C_n-1\{a_i})∩G₁与B_v\{w}有边数超过2的红色匹配，即会产生中心点为w的红色W_{1, n}.所以(C_n-1\{a_i})∩G₁必与B_v中至少|B_v|-2个点全连蓝边.又因为R_v中任意一点均与(C_n-1\{a_i})∩G₁至少连一条蓝边，R_v与B_v中|B_v|-2个点连红边，且|B_v|≥n/2+2，|(C_n-1\{a_i})∩G₁|≥n/2-1，产生红色W_{1, n}.所以若R_v∩G₂中存在点与B_v连蓝边则其在A₁中红度为0.又因为|R_v∩G₂|=p，则|A₁|≥p，|B_v|≥n/2+2，所以A₁在C_n-1中为红色K_p.B_v中必存在一点w_i与红色K_p全连红边，否则为避免产生蓝色K₃，R_v与B_v全连红边形成红色W_{1, n}.注意到若K_p与B_v\{w_i}有边数超过2的红色匹配，即R_v∩G₁，K_p和B_v会产生以w_i为中心点的红色W_{1, n}.所以K_p必与B_v中至少|B_v|-2个点全连蓝边，R_v与B_v中|B_v|-2个点全连红边，R_v与B_v产生红色W_{1, n}.

情形2  |A₁|=1时, |A|=n/2，|B|=n/2-1，|C_n-1∩G₂|=1，设此点为u.同理，B_v中不存在蓝边且R_v∩G₁中无蓝边，R_v∩G₁的点与B_v全连红边.只需确定点u的邻域即可证明定理1.已知(R_v∩G₁)∪B_v为红色K_n，若d_Kn^R(u)≥3，则形成红色W_{1, n}.因此|R_v∩G₁|≤2，uv必为红边.d_Kn^B(u)≥n-2，u若与C_n-1连一条蓝边，则会产生红色W_{1, n}，所以u与C_n-1全连红边产生红色W_{1, n}.

情形3  |A₁|=0时.n为奇数时，|A₁|≥1时证明方法与情形1和情形2类似，|A₁|=0时，n只可能为奇数，考虑图$G = {K_{2n + 1}} - {K_{\frac{{{\rm{n - 1}}}}{2}}} $，即${K_{\frac{{3n}}{2} + \frac{3}{2}}} \vee \frac{{n - 1}}{2} \cdot {K_1} $，$\left| A \right| = \frac{{n - 1}}{2} $，$\left| B \right| = \frac{{n - 1}}{2} $，此时R_v⊆G₁, B_v⊆G₁，由情形1可知B_v中不存在蓝边.R_v中亦无蓝边且B_v与R_v全连红边，形成红色W_{1, n}.定理得证.

定理2的证明.因为n为奇数时证明与偶数类似，所以本文只证明偶数情况.考虑图G=K_2n-1-K_n2+1，即K_3n2-2∨(n/2+1)K₁.令G₁=K_{n-1, n2-1}为蓝色二部图，其点集为V(G₁)=C₁∪C₂, C_i, i=1, 2为红色团.G₂=(n/2+1)K₁与C₁连蓝边，与C₂连红边.显然图G不存在红色的C_n与蓝色的K₃.所以r_K(C_n, K₃)≤$\left\lfloor {n/2} \right\rfloor $.

只需证明r_K(C_n, K₃)≥$\left\lfloor {n/2} \right\rfloor $.证明采用归纳假设法.当n=4和n=5，r(C₄, K₃)=7，r(C₅, K₃)=9，r_*(C₄, K₃)=5，r_*(C₅, K₃)=6，则r_K(C₄, K₃)=2，r_K(C₅, K₃)=2.所以假设当n≥6时，r_K(C_n-1, K₃)=$\left\lfloor {\left( {n - 1} \right)/2} \right\rfloor $.考虑图G=K_2n-1-K_n/2，即K_3n/2-1∨n/2K₁.假设任意红蓝边着色下G中不存在红色C_n和蓝色K₃，则由归纳假设可知图G中存在圈C_n-1=a₁a₂…a_n-1.令G₁=K_3n/2-1，G₂=n/2K₁, A={a_i|a_i+1∈G₁}, B={a_i|a_i+1∈G₂}.可知|A|≥n/2.G₁\C_n-1中无蓝边.若不然，G₁\C_n-1中存在蓝边u₁u₂.则d^R_Cn-1(u₁)≤1，d^R_Cn-1(u₂)≤1，此时C_n-1中存在一点与u₁u₂都连蓝边，形成蓝色K₃，矛盾.所以G₁\C_n-1为红色完全图.

注意到G₁\C_n-1与C_n-1不能有边数超过2的红色匹配u₁a_i, u₂a_j，除非j=i+1或者j=i-1，否则产生红色C_n.所以若G₁\C_n-1中存在一点u使得d^R_Cn-1(u)≥1，设为ua_i，则d^B_Cn-1(G₁\(C_n-1∪{u}))≥(n-1)-1-2=n-4.令N=N_Cn-1^B(G₁\(C_n-1∪{u}))，N∪{a_i-1, a_i+1}中不存在蓝边否则会产生蓝色K₃.所以u与N∩G₁全连蓝边否则会产生红色C_n.同理G₂\C_n-1的任意一点v，d^R_N∩G1(v)≤1，因此G₂\C_n-1与G₁\C_n-1全部连红边，产生红色C_n.若∀u∈G₁\C_n-1，d^R_Cn-1(u)=0，因为G₂\C_n-1的任意一点与C_n-1至少连一条蓝边，所以G₂\C_n-1与G₁\C_n-1全部连红边，产生红色C_n.定理得证.