兩個多色頂點Ｆｏｌｋｍａｎ數(shù)的界
2009-01-01 00:00:00邵澤輝許曉東羅海鵬
計算機應(yīng)用研究 2009年3期
(1.華中科技大學 控制科學與工程系， 武漢 430074; 2.廣西科學院， 南寧 530007)
摘 要：對于正整數(shù)a1，a2，…，ar以及無向簡單圖G， 當且僅當對G的任意一種頂點r著色，都對某個i∈{1，2，…，r}存在頂點都著有顏色i的ai階的完全子圖， 則記G→(a1，a2，…，ar)v。對于k＞max{a1，a2，…，ar}，頂點Folkman數(shù)定義為Fv(a1，a2，…，ar;k)=min{｜V(G)｜:G→(a1，a2，…，ar)v，KkG}。借助于計算機 得到了18≤Fv(2，2，2，3;4)≤Fv(2，3，3;4)≤30。
關(guān)鍵詞：頂點Folkman數(shù); 頂點著色; 上界; 下界
中圖分類號：TP301 文獻標志碼：A
文章編號：10013695(2009)03083402
Bounds for two multicolor vertex Folkman numbers
SHAO Zehui1， XU Xiaodong2， LUO Haipeng2
(1.Dept. of Control Science Engineering， Huazhong University of Science Technology， Wuhan 430074， China; 2.Guangxi Academy of Sciences， Nanning 530007， China)
Abstract:For integers a1，a2，…，ar and an undirected simple graph G， the symbol G→(a1，a2，…，ar)v means that in every rcoloring ofV(G)， there exists a monochromatic aiclique of color i for some i∈{1，2，…，r} . The vertex Folkman number is defined as Fv(a1，a2，…，ar;k)=min{｜V(G)｜:G→(a2，a2，…，ar)v，KkG}. With the help of computer search， this paper obtained 18≤Fv(2，2，2，3;4)≤Fv(2，3，3;4)≤30.
Key words：vertex Folkman number; vertex coloring; upper bound; lower bound
0 引言
V(G)和E(G)分別表示圖G的頂點集和邊集，Aut(G)表示G的自同構(gòu)群。若Aut(G)在V(G)上是可遷的，即對任意u，v∈V(G)，總存在σ∈Aut(G)使得σ(u)=v，則稱圖G是點可遷圖。
對于正整數(shù)m，n，Ramsey數(shù)R(m，n)是指最小正整數(shù)n，使得每一個n階的圖G，或者G包含Km，或者G的補圖包含Kn。如果某個圖G不含Km且G的補圖不含Kn，則稱G為(m，n)圖。對于正整數(shù)a1，a2，…，ar以及無向簡單圖G，當且僅當對G的任意一種頂點r著色，都對某個i∈{1，2，…，r}存在頂點都著有顏色i的ai階的完全子圖，記做G→(a1，a2，…，ar)v。對于k＞max{a1，a2，…，ar}，頂點Folkman數(shù)定義為
Fv(a1，a2，…，ar)=min{｜V(G)｜:G→(a1，a2，…，ar)v，KkG}
1970年，F(xiàn)olkman[1]證明對于任意正整數(shù)a1，a2以及k＞max{a1，a2}，都存在一個圖G，使得G→(a1，a2)v，KkG。Folkman研究的是2色的情形， 文獻[2]將2色推廣到多色的情形。借助于計算機， Piwakowski等人[3]得到了Fv(3，3;4)=14;2000年，Nenov[4]證明了10≤Fv(2，2，3;4)≤14；2006年，Coles等人[5]通過計算機計算得到了Fv(2，2，3;4)=14。
為了研究Fv(2，2，2，3;4)和Fv(2，3，3;4)的界，本文設(shè)計算法用于驗證： 對于正整數(shù)a1，a2，…，ar以及無向簡單圖G，圖G是否具有性質(zhì)
G→(a1，a2，…，ar)v（1）
為了方便，稱式(1)為圖G的Folkman性質(zhì)。如果G不滿足性質(zhì)(1)， 則稱G有(a1，a2，…，ar)v染色。
1 測試圖的Folkman性質(zhì)
為了研究頂點Folkman數(shù)的上界， 需要解決以下問題：對于正整數(shù)a1，a2，…，ar，以及無向簡單圖G，圖G是否具有性質(zhì)(1)。
對于3色的情形，本文給出基本算法如下（其中find設(shè)置為引用參數(shù)）:
IsGColorable（G，curlayer，a1，a2，a3，find)
{
1 if find=true then
2 return;
3 if curlayer=G的頂點數(shù)+1 then
4 {
5if G的1色頂點導出子圖含a1階的團 then
6 return;
7ifG的2色頂點導出子圖含a2階的團 then
8 return ;
9ifG的3色頂點導出子圖含a3階的團 then
10 return ;
11find true;
12return;
}
13 對G的第curlayer個頂點著第1色;
14 IsGColorable(G，curlayer+1，a1，a2，a3，find);
15 對G的第layer個頂點著第2色;
16 IsGColorable(G，curlayer+1，a1，a2，a3，find);
17 對G的第layer個頂點著第3色;
18 IsGColorable(G，curlayer+1，a1，a2，a3，find);
}
引理1 給定一個圖G，設(shè)置變量find=1，然后調(diào)用函數(shù)IsGColorable(G，1，2，3，3，find)。當find返回true， 則圖G不具有性質(zhì)G→(2，3，3，)v；否則G具有性質(zhì)G→(2，3，3)v。
證明 IsGColorable是一個遞歸算法，在算法IsGColorable中，a1=2，a2=3，a3=3，當程序到達第11、12行時，給出了一種對圖G的所有頂點的3著色。其中顏色集為{1，2，3}，且不含1色2階的團，不含2色3階的團，不含3色3階的團。之后，find變量的值為true，由第1、2行知，當find為true時，程序退出遞歸從而返回，所以，當find返回true，則圖G不具有性質(zhì)G→（2，3，3）v。當程序始終沒有到達11、12行時，則在第6行，或第8行，或第10行退出，此時，對圖G，無論怎樣著色， 要么出現(xiàn)了1色的2團，要么出現(xiàn)了2色或3色的3團，而程序結(jié)束時， find仍為1。當find返回1，則圖G具有性質(zhì)G→(2，3，3)v。
2 Fv(2，3，3;4)和Fv(2，2，2，3;4)的界
首先討論Fv(2，3，3;4)和Fv(2，2，2，3;4)的下界。
引理2 Fv(2，2，2，3;4)≥17，且如果等于17，17階的Folkman圖只能是不含4獨立集的(4，4)圖。
證明 由于任意一個不含4團的16階圖H一定含有3獨立集，并且Fv(2，2，3;4)=14，所以H中除此3獨立集之外的其他13個頂點導出的子圖有(2，2，3)v染色，這時H有(2，2，2，3)v染色。所以Fv(2，2，2，3;4)≥17。
設(shè)一個17階圖G滿足G→(2，2，2，3)v，且不含4團。如果G含有4獨立集，則類似于上述討論，由Fv(2，2，3;4)=14 (見文獻[5])可知，其他13個頂點導出的子圖有(2，2，3)v染色，這時G有(2，2，2，3)v染色。因此G不含4獨立集，此時它是一個(4，4)圖。
定理1 Fv(2，2，2，3;4)≥18。
證明 假設(shè)存在一個17階圖G滿足G→（2，2，2，3）v，且不含4團，則由引理2，G是一個17階的(4，4)圖，而17階的(4，4)-圖是惟一的，且已經(jīng)由文獻[6] 給出。對處理3色情形的算法IsGColorable作很小的修改，容易得到處理4色情形的相應(yīng)算法，利用此算法經(jīng)過計算， 圖G不滿足性質(zhì)G→(2，2，2，3)v。所以Fv(2，2，2，3;4)≥18。
Fv(2，2，2，3;4)≤Fv(2，3，3;4)，由定理1可知：
推論1 Fv(2，3，3;4)≥18。
下面討論Fv(2，3，3;4)的上界。
利用算法IsGColorable對一個34個頂點的(4，6)圖G(見文獻[7]中的第一個圖)測試，結(jié)果表明:G滿足性質(zhì)G→(2，3，3)v。由此可知Fv(2，3，3;4)≤34。但此圖的任何一個導出子圖都不滿足性質(zhì)G→(2，3，3)v。此后本文又找到了一個30階的不含4團的圖G滿足性質(zhì)G→(2，3，3)v，從而得到下述定理。
定理2 Fv(2，3，3;4)≤30
證明 利用算法IsGColorable，本文對一個不含4團的30階點可遷圖(見文獻[8]文件Cay30.g6中的第10 296個圖)測試，結(jié)果表明:G滿足性質(zhì)G→(2，3，3)v，于是Fv(2，3，3;4)≤30。
對刪掉G的一個頂點得到的29階子圖加足夠多的邊而不含K4的圖，利用算法IsGColorabl可得，這個29階的圖不能給出Fv(2，3，3;4)的上界。
利用顏色的對稱性可以減少重復搜索。在關(guān)于上述的34和30階圖的計算中， 判斷圖G是否滿足G→(2，3，3)v時，由于對第一個點著2色和3色是等價的，只需對第一個點著顏色1或顏色2。如果圖中第一個頂點和第二個頂點相鄰，則只需要考慮以下兩種情況：a)第一個頂點染顏色1，第二個頂點染顏色2；b)第一個頂點染顏色2。這樣計算效率可提高一倍。由于上述的30階圖是點可遷的，并且第一個頂點和第二個頂點相鄰，還可以進一步減小計算量，只需處理其中的第一種情況即第一個頂點染顏色1，第二個頂點染顏色2。
由定理2及Fv(2，2，2，3;4)≤Fv(2，3，3;4)可得
推論2 Fv(2，2，2，3;4)≤30。
3 結(jié)束語
對于n個頂點的圖G，算法IsGColorable的時間復雜度為O(3n)。雖然在具體的計算中復雜度會略小一些，但對于階數(shù)較大的圖，用算法IsGColorable測試性質(zhì)(1)可能難以在可接受的時間內(nèi)遍歷所有的情況。為了提高算法的效率， 除了上一章提到的方法外，還可以采用以下策略：
a)在IsGColorable中，第2行后面、第3行前面加一些控制剪枝的條件:當layer到達某個給定的數(shù)，即到達給定的層數(shù)時，判斷G的前l(fā)ayer個頂點中i色頂點導出子圖含ai階的團， 若含有則返回。
b)如果要測試的圖不是正則圖，可對測試的圖G按頂點的度遞減排序。對前面的第一個34階的圖的頂點進行度的遞減排序，這時得到的圖中第一個頂點和第二個頂點相鄰。這種方法結(jié)合上文關(guān)于對稱性的分析，計算效率也能得到較大的提高。
參考文獻：
［1］FOLKMAN J. Graphs with monochromatic complete subgraphs in every edge coloring [J]. SIAM Journal on Applied Mathematics， 1970，18(1):1924.
[2]NESETRIL J， RODL V. The Ramsey property for graphs with forbidden complete subgraphs[J]. Journal of Combinatorial Theory， Serial B，1976，20:243249.
[3]PIWAKOWSKI K， RADZISZOWSKI S P， URBRANSKI S. Computation of the Folkman number Fe(3，3;5)[J]. Journal
of Graph Theory， 1999，32(1):4149.
[4]NENOV N D. On a class of vertex Folkman graphs[J].Annuaire Univ Sofia Fac Math Inform， 2000，94:1525.
[5]COLES J， RADZISZOWSKI S P. Computing the Folkman number[J]. Journal of Combinatorial Mathematics and Combinatorial Computing， 2006，58:1322.
[6]GREENWOOD R E， GLEASON A M. Combinatorial relations and chromatic graphs[J]. Canadian Journal of Mathematics， 1955，7(1): 17.
[7]McKAY B. The largest known Ramsey(4，6)graphs[EB/OL].[20080212]. http://cs.anu.edu.au/~bdm/data/ramsey.html.
[8]ROYLE G. Transitive graphs[EB/OL].(19970116). http://people.csse.uwa.edu.au/gordon/remote/trans/index.html.
