ZUBAN.dvi

Size: px

Start display at page:

Download "ZUBAN.dvi"

衾江
7 years ago
Views:

1 第 48 卷第 2 期 2012 年 4 月兰州大学学报 ( 自然科学版 ) Journal of Lanzhou University (Natural Sciences) Vol. 48 No. 2 Apr 文章编号 : (2012) 图的一类新双变量色多项式唐晓清 1, 刘念祖 2, 王汉兴 2, 白延琴 1 1. 上海大学理学院, 上海上海立信会计学院数学与信息学院, 上海摘要 : 根据 Klaus Dohmen 等提出的图的新双变量色多项式概念, 探究了一般图关于此定义的减边公式, 利用它反复迭代后可以方便地求得任何图的新双变量色多项式, 还利用它深入探讨了一些特殊图的新双变量色多项式公式. 同时还探究了运用包含等偏序关系, 利用 Möbius 反演法和格子剖分法求得图的新双变量色多项式. 最后探讨了共点图的新双变量色多项式公式以及图的顶点和边与色多项式的关系. 关键词 : 减边公式 ; Möbius 反演 ; 共点图 ; 非同构图中图分类号 : O157.5 文献标识码 : A A class of new two-variable chromatic polynomials TANG Xiao-qing 1, LIU Nian-zu 2, WANG Han-xing 2, BAI Yan-qin 1 1. College of Sciences, Shanghai University, Shanghai , China 2. School of Mathematics & Information, Shanghai Lixin University of Commerce, Shanghai , China Abstract: A new two-variable chromatic polynomial concept of graph was proposed by Klaus Dohmen et al. A general formula was achieved by us after a hard study and is called here the Reduction Edge Formula. Any graph s chromatic polynomial could be obtained conveniently when we repeated iteration with it. Some special graphs were also studied and their chromatic polynomial formulae, i.e. their explicit expressions, were obtained. At the same time, the partial order of containing relation was studies and by using Möbius inversion method, the chromatic polynomial coefficients were obtained. By using partition lattice of the vertex set, the variable number of times was got. So in the end, the chromatic polynomials obtained. Finally, the inclusion-exclusion principle was used to get a very important formula, i.e. the chromatic polynomial formula of intersection vertex graph. Key words: reduction edge formula; Möbius inversion; intersection vertex graph; non-isomorphic graph AMS Subject Classifications(2000): 05C15 自从图的四色问题被提出后, Birkhoff 首次引进色多项式的概念, 设立 P(G, y) 表示图的色多项式, 希望以此作为解决四色问题的一个可能的方法. 此后, Whitney [1], Read [2] 进一步将此概念推广到任意图上, 建立了一些基本的结果. 比如, 色图的多项式系数为 0 [3]. 再后来, Tutte [4] 开始对图引进双变量的概念, 提出 T(G; x, y) 色多项式, 进行了很多研究, 得出一些成果. [5] 最近, Dohmen 等在弱化 Tutte 的双变量的有关恰当染色条件后, 提出新的双变量色多项式概念, 定义如下 : 设在一个没有环和复边的简单图 G=(V, E) 里, V 是顶点集, E 是边集. 令色的集合 X=Y Z, Y Z=φ, 并且设 X =x, Y =y. 这样, 对于图 G 的恰当染色, 存在映射 ϕ: V X, 对于 V 中任意不同顶点 u,v, 边 (uv) E, 并且, 对 ϕ(u) Y,ϕ(v) Y, 有 ϕ(u) ϕ(v), 也就是说, 相邻的顶点不能染集合 Y 中的同一色. 所以, 相邻的顶点染同色, 只有当这个色取自集合 Z. 为了区别这两个不同集合的染色, 本文把染集合 Y 中色称为恰当染色, 而把收稿日期 : 基金项目 : 上海市教育委员会科学基金项目 (05QZ01); 国家自然科学基金项目 ( ); 上海市教育委员会创新重点项目 (12ZZ193) 作者简介 : 唐晓清 (1972 ), 男, 湖南邵阳人, 讲师, 博士研究生, tangxiaoqing5168@163.com, 研究方向为色图与网络.

2 第 2 期唐晓清, 等 : 图的一类新双变量色多项式 107 染集合 Z 中色称为不恰当染色, 由此得到图 G 的不同的染色数, 记为 P(G; x, y), 这是一个包含两个变量 x 和 y 的多项式. 由此, 有如下新双变量色多项式计算公式 [5] : (x y) X P(G X; y). (1) X V 同时, 由于双变量在 Z =φ 时, 即 x=y 时, 新的双变量色多项式相当于普通的单变量色多项式, 故对于著名的减边公式 [2 4], 有 P(G; y, y) = P(G e; y, y) P(G/e; y, y). (2) 另外, 双变量色多项式还有一个性质 [5] : x P(G v; x, y). (3) v V 1 双变量色多项式的减边公式 1.1 推导一般来说, 直接由定义计算一个复杂图的色多项式很麻烦. 但是, 应用减边公式就使问题变得简单多了, 反复运用 P(G; y)=p(g e; y) P(G/e; y), 能够使复杂的图每一步变成两部分, 每一部分比先前的图要简单, 最终变成一些小的简单图, 从而简化计算. 人们希望能够对于双变量的色多项式也能够有类似的公式, 以便简化计算. 通过研究, 本文有如下关于双变量色多项式的 ( 减边公式 ) 定理. 定理 1 对于简单图 G=(V, E), 有 P(G e; x, y) P(G/e; x, y)+ (x y) P(G {u, v}; x, y). (4) 其中 : 顶点 u V, v V, 而且, 边 (uv)=e E. 证明先让图 G 的边 e 的两端顶点 u, v 任意染色而其余顶点正常染色, 这样的染色数共有 P(G e; x, y) 种. 但是, 当边 e 的两端顶点 u, v 染同色时要去掉, 故而要减去 P(G/e; x, y). 最后, 所去掉的部分中, 当边 e 的两端顶点 u, v 染集合 Z 中同色而其余部分正常染色, 这是容许的, 故而, 要加回来. 根据容斥原理 [6 7], 所以, 要加上 (x y) P(G {u, v}; x, y). 综前所述, (4) 式成立. 对 (4) 式, 当 x=y 时, 明显变成前面著名的单变量减边 (2) 式. 1.2 定理的公式应用举例本文将通过一个四个顶点的星形图 ( 表示为 S 4 )( 图 1), 应用双变量色多项式的减边公式得出它的色多项式. 显然, 这个星图减边后, 分解成三部分, 一个是去掉边 e 的图 ; 再减去缩去了边 e, 从而顶点 A 和 C 合并的图 ; 再加上 (x y) 乘以边 e 的两图 1 星图的减边 Figure 1 Star reduce edge by stepwise 个端点皆去掉的剩下的图, 得到如下色多项式 : P(S 4 ; x, y) = xp(p 3 ; x, y) P(P 3, x, y)+(x y) x x = (x 1)P(P 3 ; x, y)+(x y)x 2. 当然, 这里的三个顶点的路图 ( 表示为 P 3 ), 同样可以进行减边分解 ( 图 2): 图 2 路图的减边 Figure 2 Path reduce edge by stepwise 此时, 前面减边后剩下的路图也拆分成三部分, 故有 P(P 3 ; x, y) = xp(p 2 ; x, y) P(P 2 ; x, y)+(x y)x = (x 1)P(P 2 ; x, y)+(x y)x = (x 1)[x 2 x+(x y) 1]+(x y)x. 令 P(φ; x, y)=1, 最后很方便地得到星形的新双变量色多项式 P(S 4 ; x, y) = x 4 3x 2 y +3xy y. 1.3 新双变量色多项式的减边公式在圈图上的应用利用减边公式 (4), 可以很快地推导出很多类型图的新双变量色多项式公式. 比如, 对于一个有 n 个顶点的圈图 ( 表示为 C n ), 有 P(C n ; x, y) =P(P n ; x, y) P(C ; x, y)+ (x y)p(p n 2 ; x, y). (5) 反复迭代即可得到每一圈图的色多项式. 1.4 新双变量色多项式的减边公式在路图上的应用通过前面的例子易知, 一般的图, 经过反复拆分边后, 最后化成一些路图和孤立的顶点. 所以, 推导出具体的路图公式, 就显得非常有实际意义. 利用减边公式 (4), 本文推导出有 n 个顶点的路图 ( 表示为 P n ) 的新双变量色多项式公式 : P(P n ; x, y) = xp(p ; x, y) P(P ; x, y)+

3 108 兰州大学学报 ( 自然科学版 ) 第 48 卷 (x y)p(p n 2 ; x, y) = (x 1)P(P ; x, y)+(x y)p(p n 2 ; x, y). (6) 反复迭代即可得到每一路图的色多项式. 2 一些特别图的新双变量色多项式公式一般说来, 利用减边公式 (4) 进行图的分解, 虽然能够较快地算出它们的双变量色多项式, 也一定能够算出. 但是, 在图的边较少时, 计算更迅速. 故而, 在图的边数较多的情况下, 还是利用专门的公式较好. 2.1 有 n 个顶点的完全图 ( 表示为 K n ) 的新双变量色多项式 P(K n ; x, y) = yp(k ; x 1, y 1)+(x y)p(k ; x, y) = n Cn i y i (x y) n i. (7) 其中 y i = y(y 1) (y i+1), 令 y 0 = 1. 证明先任取一个顶点进行染色, 则共有两种情况. 一种情况是, 不妨先让这个顶点恰当染色, 则有 y 种方法, 而余下的是有个顶点的完全图 K, 且其顶点除此色不能再染外可以任意染色, 所以是 yp(k ; x 1, y 1); 另一种情况是, 当此顶点是不恰当染色, 有 (x y) 种方法, 而余下的是有个顶点的完全图 K, 且其顶点可以任意染色, 所以是 (x y)p(k ; x, y). 综前所述, 得出 (7) 式. 所以本文计算了如下一些简单完全图的色多项式 : P(K 2 ; x, y) = x 2 y, P(K 3 ; x, y) = x 3 3xy +2y, P(K 4 ; x, y) = x 4 6x 2 y +8xy +3y 2 6y. 定理 2 对于有 n 个顶点的完全图 K n, 有 x P(K n; x, y) = n P(K ; x, y). (8) 证明由前面的 (7) 式, 有 P(K n ; x, y)= n Cny i i (x y) n i, x P(K n; x, y) = n x [ Cny i i (x y) n i ] = Cn i y i (n i) (x y) n i 1 = n! i!(n i)! (n i) y i (x y) n i 1 = n n! i!(n i 1)! y i (x y) n i 1 = ()! i!(n i 1)! y i (x y) n i 1 = n C i y i (x y) n i 1 = n P(K ; x, y). 推论 1 由定理 2, 有 () x P(K n ; x, y) = n! x. 2.2 有 n 个顶点的轮图 ( 表示为 W n ) 的新双变量色多项式 P(W n ; x, y) =yp(c ; x 1, y 1)+ (x y)p(c ; x, y). (9) 证明先取轮图的轴心那一个顶点进行染色, 则有两种情况. 一种情况是, 不妨先让这个顶点恰当染色, 则有 y 种方法, 而余下的是有个顶点的圈图 C, 且其顶点除此色不能再染外可以任意染色, 所以是 yp(c ; x 1, y 1); 另一种情况是, 当此顶点是不恰当染色, 则有 (x y) 种方法, 而余下的圈图 C, 且其顶点可以任意染色, 所以是 (x y)p(c ; x, y). 综前所述, 得 (9) 式. 本文计算了如下一些简单轮图的色多项式 : P(W 4 ; x, y) =x 4 6x 2 y +8xy +3y 2 6y, P(W 5 ; x, y) =x 5 8x 3 y +14x 2 y 19xy+ 10xy 2 12y 2 +14y, P(W 6 ; x, y) =x 6 10x 4 y +20x 3 y 35x 2 y+ 20x 2 y 2 5y 3 +44xy 40xy y 2 30y. 2.3 有 n 个顶点的路图 ( 表示为 P n ) 的新双变量色多项式 P(P n, x, y) = xp(p, x, y) yp(p n 2, x, y)+ yp(p n 3, x, y)+ +( 1) i yp(p i, x, y)+ +( 1) yp(φ, x, y) = x n + ( 1) i (n i)x i y +( 1) n Cy <2i n 4<2i<n i=1 ( 1) i (i+1)cn i 2i xy i + ( 1) n 2 i(i+2)(i+1) C n 2 2i n 3 i 2 x2 y i + 其中 P(φ, x, y)=1. (10) 证明对于路图, 不妨先选取最左的端点开始染色. 对 P n 这个最左的端点先任意染色, 共有 x

4 第 2 期唐晓清, 等 : 图的一类新双变量色多项式 109 种可能. 而余下的是有个顶点的路图, 表示为 P, 再对 P 任意染色, 于是, 共有 xp(p, x, y) 种可能. 但是, P 这些所有可能的染色中, 当它最左边的端点是恰当染色, 并且如果它和原来 P n 最左边的端点同色的话, 是不允许的, 要减去该部分. 所以, 要再减 yp(p n 2, x, y). 但是, 所减去的部分, 还多减去了最左边三个顶点, 已知同是恰当染色而且是同色的, 而余下的是 n 3 个顶点而任意染色的情况, 所以还要加回来 yp(p n 3, x, y). 同理, 这些情况里, 还要减去 yp(p n 4, x, y). 如此反复进行, 直到没有顶点的空图 φ. 令 P(φ, x, y)=1. 最终, 得到上面的路图色多项式公式. 本文计算了如下一些简单路图的色多项式 : P(P 1 ; x, y) = x, P(P 2 ; x, y) = x 2 y, P(P 3 ; x, y) = x 3 2xy +y, P(P 4 ; x, y) = x 4 3x 2 y +y 2 +2xy y. 2.4 有 n 个顶点的圈图 ( 表示为 C n ) 的新双变量色多项式 P(C n, x, y) = (x y)p(p, x, y)+y[p(p, x, y) 2P(P n 2, x, y)+3p(p n 3, x, y)+ + ( 1) n ()P(P 1, x, y)+ ( 1) n+1 ()P(φ, x, y)]. (11) 其中 P(φ, x, y)=1. 证明对于有 n 个顶点的圈图 C n 先选任一顶点开始染色, 则此顶点可以是恰当染色或不恰当染色两种可能. 如果是不恰当染色, 则剩余部分是可以任意染色的有 n 1 个顶点的一个路图, 故有 (x y)p(p, x, y) 种情况 ; 如果此顶点是恰当染色, 则可以让有个顶点的剩余部分这个路图先任意染色, 有 yp(p, x, y) 种情况. 但是, 当剩余路图的首尾两端顶点中任一和先前的顶点同色时, 是不行的, 必须减去, 所以需要再减去此时多出来的 y 2P(P n 2, x, y). 而此时, 又多减去了剩余路图的首尾两端顶点都和先前的顶点同色的情况, 故要加上 y 3P(P n 3, x, y). 如此反复进行下去, 直到没有顶点的空图 φ, 这里 P(φ, x, y)=1. 最终, 得到上面的圈图色多项式公式. 本文计算了如下一些简单路图的色多项式 : P(C 3 ; x, y) =x 3 3xy +2y, P(C 4 ; x, y) =x 4 4x 2 y +4xy +2y 2 3y, P(C 5 ; x, y) =x 5 5x 3 y +5xy 2 +5x 2 y 5y 2 5xy +4y. 2.5 分别有 m, n 个顶点的完全二部图 ( 表示为 K m,n ) 的新双变量色多项式 P(K m,n ; x, y) = (x y)p(k m 1,n ; x, y)+ Cm 1P(K i m 1 i,n ; x 1, y 1)+(x 1) n ]. m 2 y[ (12) 证明先在二部图的一部 m 个顶点中任取一个顶点进行染色, 则有不恰当染色和恰当染色两种情况. 首先, 当此顶点是不恰当染色时, 有 (x y) 种方法, 余下的二部图 K m 1,n 可以任意染色, 故而有 (x y)p(k m 1,n ; x, y). 第二, 此顶点是恰当染色时, 有 y 种染色方法, 对于余下的二部图 K m 1,n, 则当此一部顶点余下的 m 1 个顶点中的任意 i(0 i m 2) 个顶点也染此色是可以的, 而另一部的 n 个顶点皆不能染此色. 故而能用的只能是 y 1 种恰当染色和总数为 x 1 种色, 即为 C i m 1 P(K m 1 i,n; x 1, y 1). 最后, 当此一部的 m 个顶点全染此色时候, 则此时另一部的个顶点可以任意染另外的 x 1 色中的任一色. 综合这些情况, 本文得出上面的公式. 反复运用这个公式, 就可以算出所有二部图的色多项式, 下面是一些常用二部图的色多项式 : P(K 2, 2 ; x, y) =x 4 4x 2 y +4xy +2y 2 3y, P(K 2, 3 ; x, y) =x 5 6x 3 y +9x 2 y 11xy+ 6xy 2 6y 2 +7y, P(K 2, 4 ; x, y) =x 6 8x 4 y +16x 3 y 26x 2 y+ 12x 2 y 2 +30xy 24xy y 2 15y, P(K 3, 3 ; x, y) =x 6 9x 4 y +18x 3 y 33x 2 y 6y x 2 y 2 +42xy 36xy 2 +36y 2 31y. 3 双变量色多项式的 Möbius 反演由于此种双变量色多项式定义涉及禁色格问题 [5], 本文现在用一种新的观点来理解有关新双变量色多项式. 3.1 禁色格的定义和有关性质设图 G=(V, E), Π(V) 是对顶点集 V 的一种格子剖分. 对于子集 W V, 如果由 W 构成的图 G 的子图是连通的, 就说 W 是连通的. 设 Π G 是让每个部分都是连通的这样的剖分 π 的集合. 则这样的 Π G 形成了对 Π(V) 的一个子格子剖分. 如果某种剖分 π 使得每个格子只有一个元, 则这是 Π G 里的一种最好剖分, 记为 ˆ0. 设 f(π) 是对顶点 V 的

5 110 兰州大学学报 ( 自然科学版 ) 第 48 卷用 y 种色恰当染色和 x y 种色不恰当染色的方法的总数. 这样, 1) 剖分 π 分 V 所成的每一块 B 的顶点染同一色 ; 2) 如果 B =1, 则可以取 X 中任一色 ; 如果 B 2, 则必须取 Y 中色 ; 3) 有边相连接的块, 不能取用 Y 中同一色. 现在, 本文用 π 表示剖分 π 对 V 分成的块数, 用 k 1 (π) 表示 π 中单个元的个数, 则有 x k1(π) y π k1(π) = f(σ). (13) σ Π, σπ 注 : 上式右边表示对图 G 的所有可能剖分方法总数之和. 定理 3 图的新双变量色多项式可以表达为格 [5] 子剖分的和 µ(ˆ0, π)x k1(π) y π k1(π). (14) π Π G 注 : 这里的 µ(ˆ0, π) 是 Π G 对图 G 的禁色格的反演数, 即 (14) 式中的系数是 (13) 式里的 Möbius 反演数. 证明由上面禁色格的定义, f(π) 是对顶点 V 的用 y 种色恰当染色和 x y 种色不恰当染色的方法的总数. 所以, 对于所有顶点 V 的不同剖分, 有 (13) 式中的那些方法. 根据 Möbius 反演的含义, 系数 µ(ˆ0, π) 乘以这种染色方式的变量表示式, 就是此种染色的一个双变量表示. 把所有的不同剖分以及它们的双变量表示全部加起来, 这正是双变量色多项式的定义. 故而, 就有了上面定理的结论, 即 (14) 式. 为了下面更好地理解, 本文引入如下定理 : 定理 4 设 V 是有限集, σ 为 V 的一个 p- 划分, 记为 σ =V 1 V 2 V p, 这里 V 1 V 2 V p =V, V i V j = φ, i j 时. Π V 为 V 的剖分的集合. σ, τ Π V, 若 σ 的每一个划分类都包含在 τ 的一个划分类中, 即存在偏序关系 [8] σ τ. 如果对 τ 有 τ = U 1 U 2 U m, 并且 U 1 = V 1 V 2 V n1, U 2 = V n1+1 V n2, U m = V nm V p, (p = n m ), 则有 m µ(σ, τ) = ( 1) m+p (n i 1)!. (15) i=1 证明对于集合 V 的划分 τ 而言, 由于 U 1 =V 1 V 2 V n1, 有 n 1 个子集包含于 U 1, 并且, 这些子集的任意少于 n 1 个的组合是 U 1 的真子集, 所以有 (n 1 1)! 种. 同理, 对于其他集合 U 2,, U m, 分别有 (n 2 1)!,, (n m 1)! 种真子集. 并且, 由两种划分 σ, τ 分别有 m, p 个元素, 所以, 根据 Möbius 反演的含义, 就有了上面的 (15) 式. 定理 5 设 V 是有限集, θ(v) = 2 V 是 V 的子集族, 对 A, B θ(v), 偏序关系 A B 为包含关系 A B, 则有 Möbius 反演 : { ( 1) B A, A B V, µ(a, B) = (16) 0, 其他. 证明用数学归纳法予以证明. 对集合 A, (i) 显然有 A A. 由 Möbius 反演含义, 系数为 1, 1=( 1) A A. (ii) 对任意 B=A {v 1 }, v 1 / A, 有 A B. 由 Möbius 反演含义, 系数为 1, ( 1)=( 1) B A. (iii) 同理, 对任意 B=A {v 1,, v n }, v 1,, v n / A, 有 A B. 由 Möbius 反演含义, 可知系数为 ( 1) B A. 综上所述, 就有了上面的 (16) 式. 3.2 Möbius 反演示例本文以一个有四个顶点的完全图 ( 图 3) 为例进行说明. 图 3 K 4 的示例 Figure 3 Example of K 4 利用定理 4, 可以算得有关数值为 µ(ˆ0, ˆ0) = 1, µ(ˆ0, τ 1 ) = 1, µ(ˆ0, τ 2 ) = 2, µ(ˆ0, τ 3 ) = 6, µ(ˆ0, τ 4 ) = 1. 而由分块情形明显可以看出 : k 1 (ˆ0) = 4, ˆ0 = 4, k 1 (τ 1 ) = 2, τ 1 = 3, k 1 (τ 2 ) = 1, τ 2 = 2, k 1 (τ 3 ) = 0, τ 3 = 1, k 1 (τ 4 ) = 0, τ 4 = 2. 由有关包含关系的哈斯图 ( 如图 4 所示, 小括号内为 Möbius 反演数 ), 结合定理 3, 容易得出 K 4 的色多项式为 P(K 4 ; x, y) = x 4 6x 2 y +8xy +3y 2 6y. [8] 本文再对后一种偏序关系进行示例演示. 任选一个有四个顶点的路图 ( 图 5), 来看看有关具体运用.

6 第 2 期唐晓清, 等 : 图的一类新双变量色多项式 111 y [ B y [ C P(G 2 {B}; x 1, y 1)] P(G 1 ; x, y)+ P(G 1 {C}; x 1, y 1)] [ B P(G 2 {B}; x 1, y 1)]. (17) 注 : 这里的顶点 C G 1 N(A), B G 2 N(A), 图 4 关系与系数并且 N(A) 表示图 G 内顶点 A 所有的邻点. Figure 4 Correlation and coefficients 图 5 P 4 的示例 Figure 5 Example of P 4 则由有关的包含关系的哈斯图 ( 图 6), 容易算出有关系数 : µ(ˆ0, ˆ0) = 1, µ(ˆ0, τ 1 ) = 1, µ(ˆ0, τ 2 ) = 1, µ(ˆ0, τ 3 ) = 1, µ(ˆ0, τ 4 ) = 1; 而 k 1 (τ 1 ) = 2, τ 1 = 3, k 1 (τ 2 ) = 0, τ 2 = 2, k 1 (τ 3 ) = 1, τ 3 = 2, k 1 (τ 4 ) = 0, τ 4 = 1. 所以, 根据定理 3 和定理 5, 有路图 P 4 的色多项式 : P(P 4 ; x, y) = x 4 3x 2 y +y 2 +2xy y. 图 7 共点图 Figure 7 Intersection vertex graph 证明先对顶点 A 任意染色, 有 x 种. 然后, 对余下的两个小图 G 1, G 2 先任意染色, 则有 x P(G 1 ; x, y) P(G 2 ; x, y). 但是, 当顶点 A 恰当染色时, 如果小图 G 1, G 2 有一个与顶点 A 相邻的顶点染同色, 而另外一个小图任意正常染色, 则这种情况是要去掉的. 最后, 若两边都去掉, 则重复减了, 因此要加回来. 综前所述, 有了上面的公式. 下面, 用一个简单例子来说明 ( 图 8). 从上面的示例, 可以看出, 图的色多项式里, 变量和它们的系数有内在联系. 本文利用有关的 [9] 顶点和边的关系, 可以由禁色格定义和 Möbius 反演不难写出其色多项式来. 反过来, 这也让人更深刻地理解有关数学知识的深刻的内在联系. 图 8 共点图示例 Figure 8 Intersection vertex graph example 在图 8 中, 可以看作左边是图 P 2 与右边是单点图 P 1 都与顶点 A 相连, 则根据共点公式, 有 xp(p 2 ; x, y)p(p 1 ; x, y) 图 6 P 4 的关系与系数 Figure 6 Correlation and coefficients of P 4 4 共点两图的色多项式公式曾研究了一些特殊图, 但只有很小的部分能得出漂亮的公式. 比如图 7 所示的图 G, 它可以看作由两个小图 G 1, G 2 分别和一个顶点 A 连接构成, 那么图 G 的色多项式与两个小图 G 1, G 2 的色多项式有何关系? 本文得出如下公式 : x P(G 1 ; x, y) P(G 2 ; x, y) y [ P(G 1 {C}; x 1, y 1)] P(G 2 ; x, y) C y[p(p 2 {C}; x 1, y 1)+ P(P 2 {D}; x 1, y 1)]P(P 1 ; x, y) yp(p 1 {B}; x 1, y 1)P(P 2 ; x, y)+ y[p(p 2 {C}; x 1, y 1)+ P(P 2 {D}; x 1, y 1)]P(P 1 {B}; x 1, y 1), 所以 x x (x 2 y) y[(x 1)+(x 1)] x y (x 2 y) 1+y [2(x 1)] 1 = x 4 4x 2 y +4xy +y 2 2y. 5 非同构图经过研究, 本文找到只有五个顶点的最小的非同构图 ( 图 9), 但是它们有同样的双变量色多项

7 112 兰州大学学报 ( 自然科学版 ) 第 48 卷式. 而文献 [5] 所描述的有相同色多项式的最小非同构图有六个顶点. 如能确定非同构图的色多项式不同的条件, 将是很有意义的. x 5 6x 3 y +8x 2 y +5xy 2 8xy 4y 2 +4y. 图 9 不同构的图 Figure 9 Non-isomorphic graph 定理 6 如果图 G 有 n 个顶点 m 条边, 即 V = n, E =m, 则新双变量色多项式为 x n m x n 2 y +k. (18) 注 : 这里 k 表示无穷小多项式 o(x n 2 ). 证明用第二数学归纳法予以证明. (i) 首先, 当 m=0 时, P(G; x, y)=x n, (18) 式显然成立 ; 当 m=1 时, x n 2 (x 2 y) = x n x n 2 y, (18) 式显然也成立. (ii) 接着, 假设当 m=l 时, (18) 式成立, 即 x n l x n 2 y +k, 那么 (iii) 当 m=l+1 时, 有两种情况, 一种是两条边无交点, 另一种是有交点, 本文分别给以证明. 情况 1 两边无交点时, 由前面的 (4) 式, P(G e; x, y) P(G/e; x, y)+ (x y) P(G {u, v}; x, y). 此时, 图 G 有 n 个顶点和 l+1 条边 ; 而图 G e 有 n 个顶点和 l 条边, 图 G/e 有个顶点和 l 条边, 图 G {u, v} 有 n 2 个顶点和 l 条边, 所以有 P(G e; x, y) P(G/e; x, y)+ (x y) P(G {u, v}; x, y) = [x n l x n 2 y +k 1 ] [x l x n 3 y +k 2 ]+ (x y) [x n 2 l x n 4 y +k 3 ] = x n (l+1)x n 2 y +k 4. 故 (18) 式成立. 情况 2 两边有交点时, 由前面的 (4) 式 P(G e; x, y) P(G/e; x, y)+ (x y) P(G {u, v}; x, y). 此时, 图 G 有 n 个顶点和 l+1 条边 ; 而图 G e 有 n 个顶点和 l 条边, 图 G/e 有个顶点和 l 条边, 图 G {u, v} 有 n 2 个顶点和 l 1 条边, 所以有 P(G e; x, y) P(G/e; x, y)+ (x y) P(G {u, v}; x, y) = [x n l x n 2 y +k 1 ] [x l x n 3 y +k 2 ]+ (x y) [x n 2 (l 1) x n 4 y +k 3 ] = x n (l+1)x n 2 y +k 4. 故 (18) 式仍然成立. 综合以上, 定理得证. 6 结论探讨了一般图的简化计算色多项式的问题, 得出了减边公式, 还得出很多特殊图的拆边迭代的明确公式. 从偏序的观点, 推出并应用了有关定理, 得出一般图的色多项式的系数与 Möbius 反演数的关系变量的次数与格子剖分的含义的关系. 最后还探讨了一类特殊图共点图的色多项式的拆分公式. 通过点的拆分, 大大简化了图的色多项式的计算. 参考文献 [1] Whitney H. A logical expansion in mathematics[j]. Bull Amer Math Soc, 1932, 38(8): [2] Read R C. An introduction to chromatic polynomials[j]. Combin Theory Ser B, 1968, 4(1): [3] Liu Nian-zu. Research on the sum of chromatic coefficients[j]. Or Transactions, 2003, 7(3): [4] Tutte W T. Graph theory[m]. Cambridge: Cambridge University Press, 2001: [5] Dohmen K, Pönitz A, Tittmann P. A new twovariable generalization of the chromatic polynomial[j]. Discrete Mathematics and Theoretical Computer Science, 2003, 6(2): [6] Stanley R P. Enumerative combinatorics[m]. 3 rd ed. Monterey: Wadsworth & Brooks/Cole, 1986: [7] Stanley R P. Enumerative combinatorics[m]. 4 th ed. Cambridge: Cambridge University Press, 1999: [8] 林翠琴. 组合学与图论 [M]. 北京 : 清华大学出版社, 2009: [9] Tang Xiao-qing, Wang Han-xing. Stepwise confidence interval method for finding drug s minimum effective dose in trial[j]. Drug Evaluation Research, 2010, 33(1): ( 责任编辑 : 张勇 )

834 Vol G = (V, E), u V = V (G), N(u) = {x x V (G), x u } N (u) = {u} N(u) u. 2.2 F, u V (G), G u N (u) F [10 11], G F -., G m F -, u V (G), G

834 Vol G = (V, E), u V = V (G), N(u) = {x x V (G), x u } N (u) = {u} N(u) u. 2.2 F, u V (G), G u N (u) F [10 11], G F -., G m F -, u V (G), G Vol. 37 ( 2017 ) No. 4 J. of Math. (PRC) 1, 1, 1, 2 (1., 400065) (2., 400067) :, Erdös Harary Klawe s.,,,. : ; ; ; MR(2010) : 05C35; 05C60; 05C75 : O157.5 : A : 0255-7797(2017)04-0833-12 1 1980, Erdös,