某些有向圖的幾類乘積圖的多數(shù)染色

石 美夏偉皓王紀輝

(濟南大學(xué)數(shù)學(xué)科學(xué)學(xué)院,濟南 250022)

有向圖D的多數(shù)染色是指存在一個映射c:V(D) → {1,2,…,k} 使得對任意頂點v∈V(D),出度鄰點中與它同色的個數(shù)不超過頂點v的出度的一半,則稱有向圖D是多數(shù)k-可染的。滿足這種染色的最小的k記為χm D() 。Kreutzer等[1]最先提出有向圖的多數(shù)染色這一概念,并證明每個有向圖都是多數(shù)4-可染的。然而對有向奇圈而言,多數(shù)染色一定是其正常頂點染色,即不存在單色弧,則χm≥3。因此,Kreutzer等提出:

猜想1[1]每個有向圖是多數(shù)3-可染的。

雖然這個猜想還沒有被完全解決,但是利用概率的方法證明了猜想1對一些特殊的有向圖是成立的[1],例如出度足夠大的有向圖或者出度足夠大的情況下對有向圖的入度做出一定的限制。Anastos等[2]給出了猜想1對稀疏有向圖成立的幾種情況。

本文主要將某些有向圖的幾類乘積圖作為研究對象,利用有向圈、有向路的染色的性質(zhì)以及乘積圖的結(jié)構(gòu)特點,對其多數(shù)染色開展研究,證明猜想1對這些乘積圖是成立的。

1 有向乘積圖的多數(shù)染色

定理1設(shè)m,n∈N,m,n≥2,則Pm ×Pn是多數(shù)2-可染的。

顯然,有向路、有向圈的有向乘積是滿足交換律的即Pm×Cn ＝Cn×Pm,故只需考慮其中一種情況,不妨考慮有向乘積圖Pm ×Cn。

定理2設(shè)m,n∈N,m≥2,n≥3,則Pm ×Cn是多數(shù)2-可染的。

定理3設(shè)m,n∈N,m,n≥3,如果m,n是奇數(shù),有向乘積圖Cm×Cn是多數(shù)3-可染的;否則,Cm×Cn是多數(shù)2-可染的。

如果m,n至少一個是偶數(shù),不妨設(shè)m是偶數(shù),給定映射c:V(Cm ×Cn) →{0,1,2},使得對i∈{1,…,m－1},若i是偶數(shù),c(D[Vi])＝0;若i是奇數(shù),c(D[Vi])＝1,對i＝m,c(D[Vm])＝2。在該映射下,Cm×Cn中仍不存在單色弧,因此Cm×Cn是多數(shù)2-可染的。若m和n均是偶數(shù),在上述映射下仍不存在單色弧,因此Cm ×Cn是多數(shù)2-可染的。

2 強乘積圖的多數(shù)染色

為了方便,用sD((ui,vj)) 表示在有向圖D中,頂點(ui,vj) 的出度鄰點中與其同色的頂點個數(shù)。

定理4設(shè)m,n∈N,m,n≥2,則Pm?Pn是多數(shù)2-可染的。

由于笛卡爾乘積圖和有向乘積圖均滿足交換律,因此強乘積圖也滿足交換律,故只考慮Pm?Cn。

定理5設(shè)m,n∈N,m≥2,n≥3,如果n是奇數(shù),則Pm?Cn是多數(shù)3-可染的;如果n是偶數(shù),則Pm?Cn是多數(shù)2-可染的。

證明:設(shè)有向路Pm ＝(u1,u2,…,um),有向圈Cn ＝(v1,v2,…,vn),顯然

如果n是奇數(shù),則D[Vm] 是一個有向奇圈,因此D[Vm] 定是多數(shù)3-可染的。對每個D[Vi]i(∈{1,2,…,m}),給定映射ci:D[Vi]i(∈{1,2,…,m}) → {0,1,2} 使得在每個D[Vi] 不存在單色弧并且ci≠ci＋1,i∈{1,2,…,m－1},顯然這就是強乘積圖Pm?Cn的一個多數(shù)3-染色。

如果n是偶數(shù),則D[Vm] 是一個有向偶圈,是多數(shù)2-可染的。應(yīng)用定理4中的映射進行染色,則對任意頂點(ui,vj) ∈V(Pm?Cn)Vm,sPm?Cn((ui,vj))＝1,并且在D[Vm] 中不存在單色弧。因此Pm?Cn是多數(shù)2-可染的。

定理6設(shè)m,n∈N,m,n≥3,則Cm?Cn是多數(shù)2-可染的。

如果m,n中至少有一個是偶數(shù),則D[Wj](j∈{1,2,…,n}) 或D[Vi]i(∈{1,2,…,m}) 至少有一個是有向偶圈,是多數(shù)2-可染的。因此,對每個頂點(ui,vj) ∈V(Cm?Cn),在上述映射c中,sPm?Cn((ui,vj))＝1。因此,Cm?Cn是多數(shù)2-可染的。

3 字典乘積圖的多數(shù)染色

設(shè)D1＝(V1,A1),D2＝(V2,A2),則字典乘積圖D1⊙D2＝(V(D1⊙D2),A(D1⊙D2)),其中,V(D1⊙D2)＝V1×V2＝{(u,v)|u∈V1,v∈V2},A(D1⊙D2)＝{(u1,v1)(u2,v2)|u1u2∈A(D1)或者u1＝u2且v1v2∈A(D2)}。

定理7設(shè)m,n∈N,m,n≥2,則Pm⊙Pn是多數(shù)2-可染的。

定理8設(shè)m,n∈N,m≥2,n≥3,如果n是奇數(shù),則Pm⊙Cn是多數(shù)3-可染的;如果n是偶數(shù),則Pm⊙Cn是多數(shù)2-可染的。

如果n是偶數(shù),則D[V m] 是一個有向偶圈,因此是多數(shù)2-可染的。給定一個映射c:V(P m⊙C n) →{0,1} 使得c(ui,v j)＝1,i,j的奇偶性相同;c((ui,v j))＝0,i,j的奇偶性相異。顯然,每個D[Vi]i(∈{1,2,…,m}) 都是多數(shù)2-可染的。因此,對每個頂點(ui,v j) ∈V i i(∈{1,2,…,m－1}),出度鄰點中與其同色的頂點數(shù)滿足:s Pm?Cn((ui,v j)) ≤0.5n。因此,P m⊙C n是多數(shù)2-可染的。

定理9設(shè)m,n∈N,m≥3,n≥2,若m,n均為奇數(shù),則字典乘積圖C m⊙P n是多數(shù)3-可染的;否則,C m⊙P n是多數(shù)2-可染的。

定理10設(shè)m,n∈N,m≥3,n≥3,則字典乘積圖C m⊙C n是多數(shù)2-可染的。