王雪梅,李會序

(河南工程學院 數(shù)理科學系， 河南 鄭州 451191)

先介紹一些定義:

設M(e)=max{dG(x),dG(y)},M*(G)=min{M(e)|e∈E(G)},對于圖G的一個面f,設ni(f)為f的邊界b(f)上的i-點數(shù),對于s≥2,偶圈C=v1v2…v2sv1稱為一個(2,k)-交錯圈,若dG(v1)=dG(v3)=…=dG(v2s-1)=2且dG(v2)=dG(v3)=…=dG(v2s)=k.

引理3 對于圖G,有l(wèi)a2(G)≤Δ(G).

1 結(jié)論

下面給出2個主要定理的證明.

定理1 若G為一個連通且無割邊的平面圖,Δ(G)≥2,且不含3-圈和4-圈,則或者M*(G)≤5或者存在一個(2,6)-交錯圈.

證明假設G為一個反例.即G是一個連通的平面圖,不含3-圈和4-圈,不含(2,6)-交錯圈,Δ(G)≥2,且對于任何,一條邊e,都有M(e)≥6,有以下斷言成立:

斷言2 對每個頂點v∈V(G),都有n2(v)+n3(v)≤dG(v).

設ω為定義在V(G)∪F(G)上的權(quán)函數(shù).若v∈V(G),則設ω(v)=dG(v)-4.

若f∈F(G),則設ω(f)=dG(f)-4,所以由歐拉公式得:

設新規(guī)則為:

先考慮f∈F(G):

若dG(f)≥8,由斷言1得

接下來考慮點v∈V(G),由于Δ(G)≥2,因此,dG(v)≥2.

若dG(v)=4, 則ω′(v)=ω(v)=0;

若dG(v)=5, 則ω′(v)=ω(v)=5-4=1>0;

若dG(v)≥6, 則由斷言2得

若dG(v)=2,則v與2個度大于等于6的點相鄰,又因為圖中無割邊,則v至少與3個面關(guān)聯(lián),則

定理1證明完畢.

定理2 設G是一個無割邊的連通圖,若M*(G)≤5或G含有一個(2,6)-交錯圈,則G可分解為一個森林T和一個子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.

證明對G的邊數(shù)|E(G)|進行歸納.當|E(G)|≤1時,結(jié)論顯然成立.

設G為一個|E(G)|≥2的連通圖.

若M*(G)≤5,從|E(G)|中選擇一條邊xy,使得dG(x),dG(y)≤5.設G′=G-xy.由歸納假設,可以構(gòu)造出G′的一個邊分解T′∪H′,且Δ(T′)≤max{2,Δ(G′)-4},Δ(H′)≤4,使得x,y至少與T′的一條邊關(guān)聯(lián). 此時dH′(x)≤dG(x)-2≤3,dH′(y)≤dG(y)-2≤3，令T=T′,H=H′∪{xy}，從而G=H∪T即是所要求的邊分解. 此種情況得證.

若存在一個(2,6)-交錯圈,C=x1y1x2y2…xnynx1,使得dG(xi)=2，且dG(yi)=6,n≥2,i=1,2…n.設G′=G-E(C),假設G′可以邊分解為T′∪H′,使得Δ(T′)≤max{2,Δ(G′)-4},Δ(H′)≤4. 假設每個yi都與T′中至少一條邊關(guān)聯(lián),則dH′(yi)≤dG(yi)-3=6-3=3,i=1,2…,n.令T=T′∪{x1y1,x2y2,…xnyn},H=H′∪{y1x2,y2x3,…ynx1}.因為dT(xi)=1,T為森林,而且dH(xi)=1且dH(yi)≤dH′(yi)+1≤4.dH(t)=dH′(t)≤4t∈V(H)/V(C).從而H∪T為G的滿足要求的邊分解.

推論1 若G是不含3-圈和4-圈的平面圖,Δ(G)≥2,則G可分解為一個森林T和一個子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.

推論2 每個不含3-圈和4-圈且Δ(G)≥6的平面圖G都可分解為一個森林T和一個子圖H,使得Δ(T)≤Δ(G)-4,Δ(H)≤4.

證明G可以邊分解為一個森林T和一個子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.

若Δ(G)≥6,則由推論2,G可以邊分解為一個森林T和一個子圖H,使Δ(T)≤Δ(G)≤-4,Δ(H)≤4,從而

參考文獻：

[1] 邦迪J A,默蒂U S R.圖論及其應用[M].北京:科學出版社，1984.

[2] 吳建良.邊數(shù)較少的圖的線性蔭度[J].山東大學學報:理學版,2005,40 (3):11-14.

[3] 吳建良.Halin圖的一些路分解[J].山東礦業(yè)學院學報:自然科學版,1996(15):219-222.

[4] Habib M P.Some problems about linear arboricity[J].Discrete Math,1982,41(2):219-220.

[5] Bermond J C,Fouquet J L, Habib M,et a1.On linear k-arboricity[J]. Discrete Math,1984,52(2/3):123-132.

[6] Jackson B, Wormald N C. On the linear k-arboricity of cubic graphs[J]．Discrete Math,1996，162(1/3):293-297.

[7] Aldred R E L, Wormald N C. More on the linear k-arboricity of regular graphs[J]．Australas J Combin,1998,18(1):104-197.

[8] Chen Bailiang, Fu Henglin, Huang Guoqing． Decomposing graphs into forests of paths with size less than three[J].Australas J Combin,1991,3(1):155-173．

[9] Fu Henglin, Huang Guoqing. The linear 2-arboricity of complete bipartite graphs[J]．Ars Combin,1994,38(3):309-318.

[10] Thomassen C. Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5[J]. J Combin Theory Ser B,1999,75(1):100-109．

[11] Zhang Zhenhua. Algorithmic aspects of linear k-arboricity[J]．Taiwanese J Math,1999,3(1):73-81.

[12] Zhang Zhenhua, Chen Bailiang, Fu Henglin, et al. Linear k-arboricities on trees[J]．Discrete Appl Math,2000,103 (1/3):281-287.

[13] Akiyama J.Three Developing Topics in Graph Theory[D]. Tokyo: University of Tokyo，1980.

[14] Wu Jianliang. On the linear arboricity of planar graphs[J]. J Graph theory, 1999(31):129-134.

[15] Akiyama J,Exoo G,Harary F.Covering and packing in graphs III:cyclic and acyclic invariants[J].Math Slovaca,1980(30):405-406.