石 美夏偉皓王紀(jì)輝

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

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

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

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

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

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

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

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

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

由于笛卡爾乘積圖和有向乘積圖均滿足交換律,因此強(qiáng)乘積圖也滿足交換律,故只考慮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] 是一個(gè)有向奇圈,因此D[Vm] 定是多數(shù)3-可染的。對(duì)每個(gè)D[Vi]i(∈{1,2,…,m}),給定映射ci:D[Vi]i(∈{1,2,…,m}) → {0,1,2} 使得在每個(gè)D[Vi] 不存在單色弧并且ci≠ci＋1,i∈{1,2,…,m－1},顯然這就是強(qiáng)乘積圖Pm?Cn的一個(gè)多數(shù)3-染色。

如果n是偶數(shù),則D[Vm] 是一個(gè)有向偶圈,是多數(shù)2-可染的。應(yīng)用定理4中的映射進(jìn)行染色,則對(duì)任意頂點(diǎn)(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中至少有一個(gè)是偶數(shù),則D[Wj](j∈{1,2,…,n}) 或D[Vi]i(∈{1,2,…,m}) 至少有一個(gè)是有向偶圈,是多數(shù)2-可染的。因此,對(duì)每個(gè)頂點(diǎn)(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] 是一個(gè)有向偶圈,因此是多數(shù)2-可染的。給定一個(gè)映射c:V(P m⊙C n) →{0,1} 使得c(ui,v j)＝1,i,j的奇偶性相同;c((ui,v j))＝0,i,j的奇偶性相異。顯然,每個(gè)D[Vi]i(∈{1,2,…,m}) 都是多數(shù)2-可染的。因此,對(duì)每個(gè)頂點(diǎn)(ui,v j) ∈V i i(∈{1,2,…,m－1}),出度鄰點(diǎn)中與其同色的頂點(diǎn)數(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-可染的。