某些有向图的几类乘积图的多数染色

石 美夏伟皓王纪辉

(济南大学数学科学学院,济南 250022)

有向图D的多数染色是指存在一个映射c:V(D) → {1,2,…,k} 使得对任意顶点v∈V(D),出度邻点中与它同色的个数不超过顶点v的出度的一半,则称有向图D是多数k-可染的。满足这种染色的最小的k记为χm D() 。Kreutzer等[1]最先提出有向图的多数染色这一概念,并证明每个有向图都是多数4-可染的。然而对有向奇圈而言,多数染色一定是其正常顶点染色,即不存在单色弧,则χm≥3。因此,Kreutzer等提出:

猜想1[1]每个有向图是多数3-可染的。

虽然这个猜想还没有被完全解决,但是利用概率的方法证明了猜想1对一些特殊的有向图是成立的[1],例如出度足够大的有向图或者出度足够大的情况下对有向图的入度做出一定的限制。Anastos等[2]给出了猜想1对稀疏有向图成立的几种情况。

本文主要将某些有向图的几类乘积图作为研究对象,利用有向圈、有向路的染色的性质以及乘积图的结构特点,对其多数染色开展研究,证明猜想1对这些乘积图是成立的。

1 有向乘积图的多数染色

定理1设m,n∈N,m,n≥2,则Pm ×Pn是多数2-可染的。

显然,有向路、有向圈的有向乘积是满足交换律的即Pm×Cn ＝Cn×Pm,故只需考虑其中一种情况,不妨考虑有向乘积图Pm ×Cn。

定理2设m,n∈N,m≥2,n≥3,则Pm ×Cn是多数2-可染的。

定理3设m,n∈N,m,n≥3,如果m,n是奇数,有向乘积图Cm×Cn是多数3-可染的;否则,Cm×Cn是多数2-可染的。

如果m,n至少一个是偶数,不妨设m是偶数,给定映射c:V(Cm ×Cn) →{0,1,2},使得对i∈{1,…,m－1},若i是偶数,c(D[Vi])＝0;若i是奇数,c(D[Vi])＝1,对i＝m,c(D[Vm])＝2。在该映射下,Cm×Cn中仍不存在单色弧,因此Cm×Cn是多数2-可染的。若m和n均是偶数,在上述映射下仍不存在单色弧,因此Cm ×Cn是多数2-可染的。

2 强乘积图的多数染色

为了方便,用sD((ui,vj)) 表示在有向图D中,顶点(ui,vj) 的出度邻点中与其同色的顶点个数。

定理4设m,n∈N,m,n≥2,则Pm⊗Pn是多数2-可染的。

由于笛卡尔乘积图和有向乘积图均满足交换律,因此强乘积图也满足交换律,故只考虑Pm⊗Cn。

定理5设m,n∈N,m≥2,n≥3,如果n是奇数,则Pm⊗Cn是多数3-可染的;如果n是偶数,则Pm⊗Cn是多数2-可染的。

证明:设有向路Pm ＝(u1,u2,…,um),有向圈Cn ＝(v1,v2,…,vn),显然

如果n是奇数,则D[Vm] 是一个有向奇圈,因此D[Vm] 定是多数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的一个多数3-染色。

如果n是偶数,则D[Vm] 是一个有向偶圈,是多数2-可染的。应用定理4中的映射进行染色,则对任意顶点(ui,vj) ∈V(Pm⊗Cn)Vm,sPm⊗Cn((ui,vj))＝1,并且在D[Vm] 中不存在单色弧。因此Pm⊗Cn是多数2-可染的。

定理6设m,n∈N,m,n≥3,则Cm⊗Cn是多数2-可染的。

如果m,n中至少有一个是偶数,则D[Wj](j∈{1,2,…,n}) 或D[Vi]i(∈{1,2,…,m}) 至少有一个是有向偶圈,是多数2-可染的。因此,对每个顶点(ui,vj) ∈V(Cm⊗Cn),在上述映射c中,sPm⊗Cn((ui,vj))＝1。因此,Cm⊗Cn是多数2-可染的。

3 字典乘积图的多数染色

设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设m,n∈N,m,n≥2,则Pm⊙Pn是多数2-可染的。

定理8设m,n∈N,m≥2,n≥3,如果n是奇数,则Pm⊙Cn是多数3-可染的;如果n是偶数,则Pm⊙Cn是多数2-可染的。

如果n是偶数,则D[V m] 是一个有向偶圈,因此是多数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}) 都是多数2-可染的。因此,对每个顶点(ui,v j) ∈V i i(∈{1,2,…,m－1}),出度邻点中与其同色的顶点数满足:s Pm⊗Cn((ui,v j)) ≤0.5n。因此,P m⊙C n是多数2-可染的。

定理9设m,n∈N,m≥3,n≥2,若m,n均为奇数,则字典乘积图C m⊙P n是多数3-可染的;否则,C m⊙P n是多数2-可染的。

定理10设m,n∈N,m≥3,n≥3,则字典乘积图C m⊙C n是多数2-可染的。