一類新的染色問題

韓淑芹

(青島工學(xué)院 基礎(chǔ)教育學(xué)院, 山東 膠州 266300)

1 主要結(jié)果

定理1 若G=L(H)且p≥4，則圖G的全色極大團(tuán)染色等價(jià)于圖H的邊覆蓋染色.

推論1 Gupta定理等價(jià)于下面兩種情形

(1)若G=L(H)且p≥4，則p- 1≤χmaxcT(G)≤p.

(2)若G=T(H)且p≥4，則p- 1≤χmaxcT(G)≤p.

證明(1)可由定理1得出.

(2)將H的頂點(diǎn)染同種顏色，再由定理1可得結(jié)果.

定理2 若χmaxcT(G)=p，χmaxcT(H)=q,則χmaxcT(G[H])=pq.

證明由于E(G[H])={wijwkl∶uiuk∈E(G)或i=k,vjvl∈E(H)}，則G[H][5]的最小極大團(tuán)點(diǎn)數(shù)為pq，故有χmaxcT(G[H])≤pq.下給出G[H]的一個(gè)pq-全色極大團(tuán)染色.

令f:V(G)→{1,2,…，p},V(H)→{1,2,…,q},則f是圖G,H的一個(gè)全色極大團(tuán)染色.G中的點(diǎn)被分為p個(gè)子集，染有顏色i的點(diǎn)集記為Vi，1≤i≤p.令

f((ui,vj))=f(vj)+(i-1)q,

ui∈Vi,vj∈V(H).

G[H]的極大團(tuán)形式為(ui,vj),(uk,vl),ui,uk∈G′,vj,vl∈H′,G′H′分別為G,H的極大團(tuán).顯然G的每個(gè)極大團(tuán)pq種顏色均出現(xiàn)，從而有χmaxcT(G[H])≥pq.

定理3 若p-1≤χmaxcT(G)≤p,q-1≤χmaxcT(H)≤q，則有

χmaxcT(G×H)=min{χmaxcT(G),χmaxcT(H)}.

證明由于E(G×H)={wijwkl,i=k和vjvl∈E(H)或j=l和uiuk∈E(G)}，則G,H的極大團(tuán)仍為G×H[5]的極大團(tuán).不妨設(shè)χmaxcT(G)≤χmaxcT(H).

令f∶V(G)→{1,2,…，χmaxcT(G)},V(H)→{1,2,…，χmaxcT(H)},下對G×H的點(diǎn)進(jìn)行染色.令f((ui,vj))=f(ui)⊕(j-1),ui∈V(G),vj∈V(H),⊕表示mod(χmaxcT(G))，其中(χmaxcT(G)-1)⊕1=χmaxcT(G).G×H的極大團(tuán)有以下兩種形式：

(1) (ui,vj),ui∈G′,G′為G的極大團(tuán)，對某一固定的j,1≤j≤n,vj∈V(H).

(2) (uk,vl),vl∈H′,H′為H的極大團(tuán)，對某一固定的i,1≤i≤m,ui∈V(G).

顯然第(1)種形式的極大團(tuán)χmaxcT(G)種顏色均出現(xiàn)，第(2)種形式的極大團(tuán)χmaxcT(H)種顏色均出現(xiàn).而χmaxcT(G)≤χmaxcT(H)，從而有χmaxcT(G×H)≥χmaxcT(G)

由于G×H的最小極大團(tuán)為min{G′,H′}，故有χmaxcT(G×H)≤min{p,q}

(1)χmaxcT(G)=p,χmaxcT(H)=q. 結(jié)論顯然成立.

(2)χmaxcT(G)=p-1,χmaxcT(H)=q.則有p-1≤q.

①p=q+1,有p-1≤χmaxcT(G×H)≤q=p-1. 結(jié)論成立

②p

同理可證χmaxcT(G)=p,χmaxcT(H)=q-1,χmaxcT(G)=p-1,χmaxcT(H)=q-1的情形.

2 待研究的問題

已經(jīng)得到若G=L(H)或T(H)，有p-1≤χmaxcT(G)≤p.那么是否含全圖或線圖的圖類中也有此結(jié)論？滿足χmaxcT(G)=p的圖類有哪些？另外可以定義全色最大匹配染色，全色極大星染色，全色最長路染色等.我們將進(jìn)一步研究有此類條件限制的染色問題.

[1] Miao L Y,Liu G Z.Edge covering coloring and fractional edge covering coloring[J]. Journal of Systems Science and Complexity,2002,15(2):187-193.

[2] Miao L Y,Pang S Y.Classification of graphs on edge covering coloring[J].Journal of Math(PRC),2001,21(4):368-372.

[3] 王紀(jì)輝，劉桂真.圖的邊覆蓋染色與分?jǐn)?shù)邊覆蓋染色[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2005,40(3):1-4.

[4] Bondy J A,Murty U S R.Graph theory with applications[M].New York:Macmillan,1976.

[5] Klavzar S.Coloring graph products-A survey[J].Discrete Mathematics,1996,155: 135-145.