關于圈對完全圖的多色Ramsey數

劉大瑾， 白路鋒

(南京理工大學泰州科技學院 江蘇泰州225300)

0 符號說明

本文中的圖都是指簡單圖.設圖G=(V，E)，V為頂點集，E為邊集．如果V'?V(G)，則以V'為頂點集，以2個端點均在V'的邊集組成的圖，稱為圖G的點導出子圖，記為G［V'］．用Γ(u)表示u的鄰域，即u的所有鄰點構成的集合，由Γ(u)產生的點誘導子圖記為G'［Γ(u)］．如果E'?E(G)，則以E'為邊集，以E'中邊的所有端點為頂點集組成的圖，稱為圖G的邊導出子圖，記為G［E'］．分別用G1，G2，…，Gm表示圖，(k+1)色Ramsey數rk+1(C2m，…，C2m，Kn)是指滿足如下條件的正整數N:當用(k+1)色c1，c2，…，ck+1給完全圖KN邊著色時，總存在某個 j∈{1，2，…，k}，使得 C2m?G'［Ecj］或者 Kn?G'［Ec(k+1)］，這里 Ecj表示用顏色 cj染色的邊集．α(G)表示圖G的獨立數．f(n)、g(n)分別表示關于n的函數，f(n)≤(1+o(1))g(n)是指對于任意ε＞0，總存在一個正整數N，使得n＞N時有f(n)≤(1+ε)g(n)．定理證明中要用到高斯超幾何函數［1］

當x∈(0，+∞)時，fm(x)是正的單調減少的凸函數，且fm(x)＞(log(x/m)-1)/x，x＞m．

1 rk+1(C2m，…，C2m，Kn)上界的證明

文獻［2］研究了 r(C2m，Kn)，文獻［3］研究了 rk+1(C4，…，C4，Kn)，本文研究了更一般的情況 rk+1(C2m，…，C2m，Kn)．

引理1［4］設圖G頂點數為N，平均度為d．設Gv是v的鄰點導出子圖，平均度不超過a，則

定理1 當n足夠大時，rk+

證明 設 N=rk+1(C2m，…，C2m，Kn)-1，用 c1，c2，…，ck+1種顏色對 Kn邊著色，使得 G'［Ec1］，G'［Ec2］，…，G'［Eck］中分別不含有 C2m．設 G*=G'［Ec1］∪G'［Ec2］∪…∪G'［Eck］，由 N 的設法可知 n-1 ＞ α(G*)．下面推導出G*的平均度以及G'［Γ(v)］的平均度．

圖F的Turán數是指N個頂點的圖中不含有圖F的最大邊數，用ex(N，F)來表示．在文獻［3］中有ex(N，C2m)≤q1m，因為 G'［Ecj］中不含有 C2m，j=1，2，…，m，從而 G'［Ecj］的平均度最多為 2q1m，故有d(G*)≤2q1m

設Ni為G*中度為i的點的個數，則對于?ε＞0有

設H為G*中度小于(1+ε)d的點產生的誘導子圖，由(2)可知H的階至少為N-N/(1+ε)=εN/(1+ε)。取ε=1，則H的階至少為N/2，H的最大度小于2d(由H的設法可知)．設Δ(H)為H的最大度，則Δ(H這里 q2=q2(m，k)．

由于H是G*的子圖，故H不含有c1，c2，…，ck顏色的C2m．對于H的任意一點u，設H'［Γ(u)］為u的鄰域在H中的誘導子圖，則H'［Γ(u)］也不含有c1，c2，…，ck顏色的C2m．用上述同樣的方法可得H'［Γ(u)］的最大度 Δ(H'［Γ(u)］)≤q2

由于H是G*的誘導子圖，故H的獨立數不超過G*，即n-1≥α(G*)≥α(H)．H的平均度記為d(H)，顯然d(H)≤Δ(H)，由(1)及高斯超幾何函數的性質可得

［1］ Li Yusheng，Rousseau C C，Zang Wenan.Asymptotic upper bounds for Ramsey functions［J］.Graph Combinatorics，2001，17(1):123-128.

［2］ Yair C，Li Yusheng，Rousseau C C，et al.Asymptotic bounds for some bipartite graph:complete graph Ramsey numbers［J］.Discrete Mathmatics，2000，220(1/2/3):51-56.

［3］ Alon N，R?dl V.Sharp bounds for some multicolor Ramsey numbers［J］.Combinatorica，2005，25(2):125-141.

［4］ Li Yusheng，Rousseau C C.On book-complete graph Ramsey numbers［J］.J Combin Theory:Ser B，1996，68(1):36-44.