李婷婷 張 霞

( 山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,250358,濟(jì)南 )

1 引 言

路劃分問(wèn)題起源于Gerencsér和Gyárfás[1](1967年)提出的一個(gè)基本的命題: 對(duì)于n個(gè)頂點(diǎn)的完全圖Kn的任意的一個(gè)2-邊染色, 它的頂點(diǎn)集V(Kn)可以被劃分成一條紅色路和一條藍(lán)色路. 這里的空集和單點(diǎn)可以看作是染任意顏色的一條路. 1979年，Lehel猜想用圈代替上述命題中的路結(jié)論仍然成立. 對(duì)于n很大時(shí)Lehel猜想在文獻(xiàn)[2]和[3]中被證實(shí), 并且在2010年由Bessy和Thomassé[4]證得對(duì)所有的n都成立.

對(duì)于超圖的情形, 本文先介紹論文中所用的一些基本概念和相關(guān)符號(hào)表示, 若未提及的概念和符號(hào)表示請(qǐng)參考文獻(xiàn)[5]和[6].

一個(gè)k-一致超圖H, 有l(wèi)條超邊e1,e2,e3,…,el滿(mǎn)足對(duì)任意的i∈[l-1], 有|ei∩ei+1|=1并且對(duì)于2≤i+1

圖G(或超圖H)的一個(gè)邊染色是從邊集E(G)(或E(H))到顏色集的一個(gè)映射φ:E(G)→{1,2,3,…,k}(或E(H)). 上述稱(chēng)為圖G(或超圖H)的k種顏色的邊染色, 簡(jiǎn)記為k-邊染色. 本文主要討論2-邊染色, 一般用紅色和藍(lán)色來(lái)敘述.

2013年, Gyárfás和Sárk?zy[7]提出了一個(gè)關(guān)于完全的3-一致超圖的單色劃分的問(wèn)題.

2018年,Bustamante, Hán和Stein證得下面的引理1.

值得注意的是對(duì)于放松圈(loose cycle)上述結(jié)論同樣成立. 另外，引理1中ηn可以被改進(jìn).

目前對(duì)于完全超圖的邊染色的單色劃分的研究結(jié)果相對(duì)較少, 對(duì)于完全的k-部k-一致超圖的邊染色的單色劃分問(wèn)題還沒(méi)有相關(guān)的結(jié)果, 完全的k-部k-一致超圖相對(duì)于完全超圖研究起來(lái)更復(fù)雜, 對(duì)邊的要求更苛刻. 本文研究均衡的完全3-部3-一致超圖的單色放松路的劃分, 為以后研究一般的k-部k-一致超圖的單色劃分問(wèn)題打下基礎(chǔ).

2 結(jié)論及其證明

證s≤2時(shí)，結(jié)論顯然成立. 下面討論s≥3的情況. 在以下證明中，頂點(diǎn)的下標(biāo)是指該點(diǎn)所屬的超圖的部，比如意味著w2∈V2.

證因?yàn)閨W|≥s+1,PR和PB最多能夠覆蓋2s-1個(gè)點(diǎn). 考慮兩種情況.

性質(zhì)2PR和PB都是正常的放松路.

2) |V(PR)|=2t+1，其中整數(shù)t≥2, 即PR包含至少2條超邊.PR為{v1,v2,v3}中的某個(gè)點(diǎn), 注意V(PB)={u2,u3}，令集合V=ev={vi,vj}(其中i≠j,i,j∈{1,2,3}).由情形1)知超邊viwjwk,vjwiwk(其中i,j,k∈{1,2,3},i≠j≠k)為染藍(lán)色，則PR′=PRe和PB′={viwjwk}∪{wkwivj}與假設(shè)矛盾，故綜上所述得放松路PB是正常的.

此時(shí)可知兩條放松路PR,PB均為正常的路, 且很容易得其中放松路PR至少有2條超邊，否則PR={v1,v2,v3}且PB={u1,u2,u3}，類(lèi)似性質(zhì)2中的情形1)知超邊viwjwk(其中i,j,k∈{1,2,3},i≠j≠k)為染藍(lán)色，超邊uiwjwk(其中i,j,k∈{1,2,3},i≠j≠k)為染紅色. 由對(duì)稱(chēng)性不妨設(shè)u2v3w1為紅色，則PR′=PR∪{v3u2w1}∪{w1u3w2}∪{w2u1w3}與假設(shè)|V(PR)|+|V(PB)|是最大矛盾. 下面我們令放松路PR的第一條超邊為f={x1,x2,x3}, 最后一條超邊為e={v1,v2,v3}; 令放松路PB的最后一條超邊為g={u1,u2,u3}. 對(duì)于超邊f(xié),e,g中的二度點(diǎn)分別為x,v,u它們分別是{x1,x2,x3}, {v1,v2,v3}, {u1,u2,u3}中的某個(gè)點(diǎn), 令集合X=fx,V=ev,U=gu分別表示超邊f(xié),e,g中去掉二度點(diǎn)以外的點(diǎn)的集合; 取W′?W, 且W′={w1,w2,w3}. 其中X,V是對(duì)稱(chēng)的，從而對(duì)于X,V,U的所有可能的隨機(jī)組合，我們可以分為兩種情形進(jìn)行具體討論.

情形1：存在超邊e″={xi,vj,uk}, 其中xi∈X,vj∈V,uk∈U，且i,j,k∈{1,2,3},i≠j≠k.

由超邊e″={xi,vj,uk}知Xxi=xj或xk，Vvj=vi或vk，Uuk=ui或uj，這里我們只證明其中一種，其他可類(lèi)似得證. 考慮Xxi=xj，Vvj=vi，Uuk=ui，由已知超邊viwjwk，vjwiwk為藍(lán)色，超邊uiwjwk，ukwiwj為紅色. 下面討論超邊e″，如果超邊e″為染紅色, 則PR′=PRf∪e″∪{ukwiwj}∪{wjuiwk}和PB′=PBg(當(dāng)放松路PB恰有一條邊時(shí)，PB′={vi,uj})與假設(shè)|V(PR)|+|V(PB)|是最大矛盾. 如果超邊e″為染藍(lán)色, 則新的放松路PR′=PR{f,e}(當(dāng)放松路PR恰有兩條超邊時(shí)，PR′={xj,vk})和PB′=PB∪e″∪{vjwiwk}∪{wkwjvi}與假設(shè)|V(PR)|+|V(PB)|是最大矛盾.

情形2：不存在超邊e″={xi,vj,uk}, 其中xi∈X,vj∈V,uk∈U，且i,j,k∈{1,2,3},i≠j≠k.

3 可進(jìn)一步研究的問(wèn)題

我們討論了關(guān)于均衡的完全3-部3-一致超圖的任意2-邊染色的單色放松路的劃分問(wèn)題, 那么有沒(méi)有其他的工具使關(guān)于均衡的完全3-部3-一致超圖的單色劃分問(wèn)題得到更好的結(jié)果? 對(duì)于均衡的完全k-部k-一致超圖的任意r-邊染色的單色劃分問(wèn)題呢? 因此, 我們有以下兩個(gè)可以進(jìn)一步研究的問(wèn)題.

問(wèn)題2對(duì)于均衡的完全3-部3-一致超圖的任意的2-邊染色, 至少存在多少條點(diǎn)不交的單色放松路能夠?qū)⒃摮瑘D的所有點(diǎn)全部覆蓋?

問(wèn)題3對(duì)于均衡的完全k-部k-一致超圖的任意的r-邊染色(r≥2),存在多少個(gè)點(diǎn)不交的單色放松路或單色放松圈能夠?qū)⒃摮瑘D的所有點(diǎn)全部覆蓋?