（应用数学专业论文）关于某些图类的分数色数.pdf

摘要 文中给出了一些图类的分数色数，并根据这些结果得到了其中一些图类 的顶点色数 在第一部分中，我们主要介绍了分数染色的三种不同定义，给出了这 三者之间的等价性证明并且作为准备，列出了文中将要用到的一些性质 和定理在第二部分中，考虑了邻接矩阵第一行分别为0 1 1 0 0 0 0 1 1 和 f 0 1 0 1 0 0 0 0 1 0 1 1 的礼阶循环图，得到了它们的分数色数，以及邻接矩阵第 一行为f 0 1 1 0 0 0 0 1 1 1 的n 阶循环图当n 不是3 的倍数时的顶点色数在 第三部分中介绍了当七= 2 时的广义p e t e r s o n 图的概念，给出了其中一类 图的分数色数以及顶点色数在第四部分中通过对k n e s e r 图的一些性质的 考察，在k n e s e r 图与外平面图之问建立同态关系，从而得到了外平面图的 分数色数与顶点色数 a b s t r a c t i nt h i sp a p e r ，w e g e tt h e f r a c t i o n a lc h r o m a t i cn u m b e ra b o u ts e v e r a lk i n d s o fg r a p h s a n da c c o r d i n gt ot h e s er e s u l t sw eg e tt h ec h r o m a t i cn u m b e ro n t h e s eg r a p h s i ns e c t i o no n e ，w ei n t r o d u c et h r e ed i f f e r e n t d e f i n i t i o n so n t h ef r a c t i o n a lc h r o m a t i cc o l o r i n ga n dp r o v et h ee q u i v a l e n c er e l a t i o nb e t w e e n t h e m t h e nw es h o ws o m ep r o p e r t i e sa n dt h e o r e m sf o rl a t e ru s e 。i ns e c t i o n t w o ，t h ec i r c u l a rg r a p h sw i t ho r d e r 他 m a t r i xi s 0 1 1 0 0 0 0 1 1 a n d 0 1 0 1 0 0 一 t h a tt h ef i r s tr o wo ft h e i ra d j a c e n t 0 0 1 0 1 a r e c o n s i d e r e da n dw eo b t a i n t h ef r a c t i o n a lc h r o m a t i cn u m b e ro ft h e m ji n c l u d et h ec h r o m a t i cn u m b e r o f t h eg r a p h sw h o s e f i r s tr o wo ft h ea d j a c e n tm a t r i xi s 【0 1 1 0 0 0 0 1 1 j u s tw h i l e ni sn o tt h em u l t i p l eo f3 i ns e c t i o nt h r e e ，t h ec o n c e p t i o no ft h ep e t e r s o n g r a p hi s i n c i t e da n dt h eh a c t i o n a lc h r o m a t i cn u m b e ra n dt h ec h r o m a t i c n u m b e ro fo n ek i n do ft h e ma r eg i v e n i ns e c t i o nf o u r ，b yr e s e a r c h i n gt h e d r o p e r t i e so fk n e s e rg r a p h s ，w e c o n s t r u c tt h eh o m o m o r p h i s m 咖b e t w e e n t h e k n e s e rg r a p ha n dt h eo u t e r p t a n eg r a p h s ot h ef r a c t i o n a lc h r o m a t i c n u m b e r a ，n dc h r o m a t i cn u m b e ra r eo b t a i n e d 1 1 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包括其他人已经发表或撰写过的研究成果，也不包 含为获得西北师范大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 签名：睦馥乙日期：盘丝：量! 丛 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 显叠查： 导师签名： 红一 拦 1 丛 引言 引口 顶点色数作为图的一个极其重要的参数，一直以来都是图论工作者所研究的热点问题 之一许多著名的数学家在对这个问题的探索过程中得到了很多非常经典的结果，例如著 名的b r o o k s 定理，g r 6 t z s c h 定理，四色定理等，然而确定图的顶点色数的确是一个n p 一困 难问题为了能够更进一步的研究它，数学家们引入了如圆色数，列表色数，分数色数等的 一系列与顶点色数有着密切关系的图参数在这篇论文中，我们讨论的主要对象就是图的 分数色数 在1 9 7 3 年，h i l t o n ，r a d o 和s c o t t 在文献1 4 1 中首次提出了图的分数染色这一概念， 他们在这篇文章中证明了：所有平面图的分数色数都小于5 很快，s c o t t ，s t a h l ，c l a r k e 和j a r n i s o n ，b o l l o b d s 以及t h o m a s o n 等人分别在文献f 2 2 ，4 ，1 9 ，2 1 1 中对它作了最初的 研究，并得到了一些结果此后，在这一方面的研究便逐渐地展开了，见文献2 3 2 8 1 出于分数色数为顶点色数提供了一个下界，所以，研究图的分数色数对于我们去更 进一一步的研究图的顶点色数有着很重要的意义因此，分数色数作为图的重要参数之一， 是非常具有研究价值的在本文中，我们主要考虑了这样一些图类：邻接矩阵第一行分 别为f 0 1 1 0 0 0 0 1 1 1 和f 0 1 0 1 0 0 0 0 1 0 1 的n 阶循环图；= 2 时的广义p e t e r s o n 图； 外平面图并根据这些图的性质给出了它们的分数色数，然后再结合了b r o o k s 定理和 g r j t z s c h 定理很容易地得到了其中一些图( 包括阶数n 不是3 的倍数的邻接矩阵第一行为 f 0 1 1 0 0 0 0 1 1 的循环图，当= 2 时的广义p e t e r s o n 图和围长大于3 的外平面图) 的顶 点色数 从1 8 5 2 年四色问题的提出至今，还没有人能够真正从逻辑上对它给出证明，所以，对 于平面图的顶点染色问题便引起了人们的极大兴趣由于图的分数色数不超过它的顶点色 数，所以很自然的就会产生这样的问题：四色定理对于分数色数是否成立? 也就是说，如果 不依赖四色定理本身，是否能够从逻辑上证明：所有平面图的分数色数最多是4 7 然而这个 答案在目前是否定的在h i l t o n ，r a d o 和s c o t t 在文献 1 4 】中证明了所有平面图的分数色 数都小于5 之后，就再没有人能够对这个结果作进一步的改进由此可见，对于平面图的分 数染色的研究还是很有价值的早在1 9 5 9 年，g r s t z s c h 证明了：对于围长至少是4 的平面 图来说，它的顶点色数最多是3 在本文中，我们首先给出了外平面图分数色数，然后再经 过讨论得到了这样一个结论：对于围长至少是4 ，且奇围长存在的外平面图来说，它的顶点 色数恰好就是3 关于分数染色产生出了许多不同的定义方式，参见文献 1 ，2 ，3 ，4 ，5 那么相应地，也 出现了许多不同的名称，如多色数( m u l t i e h r o m a t i cn u m b e r ) ，集合一色数( s e t c h r o m a t i c 1 1 1 l m b e r ) 、回归色数( u l t i m a t ec h r o m a t i cn u m b e r ) 等等本文共涉及了文中将用到的三种定 引言 义方式，即分数染色，分数团和a ：b 染色在文章的第一部分中，我们给出了这三种定义并 且汪明了它们之间的等价关系，并分别给出了在不同的定义之下的分数色数所具有的重要 性质在文章的第二至第四部分中应用了这些定义和性质得到了以上所述的一些结果 从1 9 7 3 年分数染色的提出到现在，尽管在国外已经有一些人在从事这方面的研究，但 是在该领域的总体研究水平仍处于很不完善的阶段，还存在许多尚待解决的问题正如前 文中所提到的，分数染色具有很多不同形式的等价定义，这无形中就决定了研究分数染色 时方法上的多样性和灵活性，为我们在这一方面的研究提供了无限广阔的空问因此，在这 方面还有大量的工作需要我们去潜心研究、相信在这个领域的研究一定会取得长足的发展 2 5 t 图的分数染色的三种等价定义及其性质 5 1 图的分数染色的三种等价定义及其性质 关于图的分数染色有很多不同的定义方式，可参阅文献 1 ，2 3 ，4 ，5 l 在这一部分中， 我们主要给出了文中将用到的也是相对更重要的三种定义，即：分数染色，分数团和a ：b 染色并且给出了相应的等价性证明 定义1 1 【6 】设g 是一个图，s = s 1 ，岛， _ ，：5 一 0 ，1 满足：对v u y ( g ) ，( ) 1 u 令 昌) 是g 的所有独立集的集合若映射 f 则称，是g 的一种分数，( 鼠) 染色 = l x ，( g ) = m i n _ 厂( & ) 1 ，是图g 的分数染色 t = 1 如果我们设s 。，& 表示图g 的顶点集合关于独立集的一个最小划分，显然有 t = ) ( ( g ) ( 图g 的点色数) ，再设，( & ) = 1 ，i = 1 ，t ，其它余独立集所对应，的值为零，那 么显然这样构造的，就是一种分数染色，再由) ( ，( g ) 的定义就有x ，( g ) ) ( ( g ) 性质1 1 ( 6 j 设g 是一个图，则 州g ) 瓣，其愀g ) 表示图g 的独域 性质1 2 【7 】设g 是一个图，则x j ( g ) 是有理数，且相应的分数染色，( & ) 一学，这里 & s ，n z 十，q = 1 d e t a l ( a 是n n 的0 ，1 矩阵) 由定义11 知道，) ( ，( g ) 实际上是目标函数为r a i n ，( s ) ，约束条件为：对v v v ( g ) ，( & ) 1 ，以及对弧s ，( & ) 20 的线性规划的解由c r & m e r 法则 很容易知道从线性等式，慨) = 1 ，v v v ( g ) 解得，( & ) = 警，且a z + ，口= 口e s 。 i d e t a ( a 是竹乱的0 ，l 矩阵) ， 定义1 2 【8 】设g 是一个图，8 = s 1 ，岛， g ：v ( a ) 一【0 ，1 】满足：对v s 8 ，9 ( ) 1 s 。 分数团的权重 s 是g 的所有独立集的集合若映射 则称g 是g 的一个分数团g ( v ) 是 y f g ) 性质1 孙i 设g 是一个图，则 ) ( ，( g ) = m & x 9 ( ) b 是图g 的一个分数团) y ( g ) x f ( g ) 是目标函数为m i n f ( s o ，约束条件为：对v v 矿( g ) ，( s ) 1 ，以及对 v 鼠s ，( & ) 0 的线性规划的解而由定义1 2 知道，最大的分数团权重是目标函数为 3 1 图的分数染色的三种等价定义及其性质 i n 3 , x 9 ( 口) ，约束条件为：对v s 5 ，g ( v ) 1 ，以及对v v v ( g ) ，0 f ( v ) 1 的 v ( g )u 线性规划的解，恰好就是原线性规划的对偶问题的解，所以图g 的最大的分数团权重就等 于它的分数色数这就说明定义1 2 与定义1 1 是等价的并且对图g 若能找到它的一个 分数团就可以确定x s ( g ) 的一个下界 定义1 3 n 图g 的a ：6 染色，就是指给g 中各顶点分配一个集合 l ，2 ， 的b 元 子集，使得相邻顶点的集合不交 定理1 1 设g 是一个图，则 x s ( g ) = i n f a b g 存在o ：6 染色) 证明以下分两步进行证明： 1 ) x s ( g ) i n f a b l g 存在a ：6 染色 任取图g 的一个a ：b 染色c ，对v v v ( g ) ，c ( v ) 就表示分配到顶点 上的b 元集合， 由a ：b 染色的定义知道，对v u v e ( g ) ，有c ( u ) nc ( v ) = 令s = ( y ( g ) h c ( u ) ) ， 且f ( s i ) = i 1 ，i = 1 ，2 ，n n n n - b 集厶s 中的顶点它们的颜色集合均有公共元素i ，所 以& 是独立集，且对v v i ( g ) ，它恰在b 个& 中因此有，( & ) = 1 所以这样构造 v e 的，是一个分数；染色，即x s ( g ) i n f o 6 f g 存在：6 染色) 2 ) x s ( a ) i n f n 6 g 存在。：6 染色 由性质12 就可以假设x s ( g ) = ：( o ，b z 十) 令5 = 岛，+ 1 ，s ，b i 一1 of 是g 的所有独立集的集厶) 相对应的分数染色，( & ) = ：6 一。1 ：一。；，这里a i 、u 1 * = l 十1 z + ，i = 1 ，2 ，t 下面将s l 复制a ，个并重新编号为s l ，岛，s a 。；将岛复制a 2 个并重 新编号为s a 。+ 。，& 。+ ，l + a 2 ；继续这一过程直到将& 复制a t 个并重新编 号为& 。+ + 毗- 。+ 1 ，扣佃一。忆，这样就得到了a 个独立集，显然，对v v v ( g ) ， 它恰好出现在b 各独立集中 以下构造a ：b 染色：对v v v ( g ) ，令c ( v ) = 倒u & ，i = 1 ，2 ，n ，由于 恰在b 个独立集中，所以l c ( v ) l = b ，且对v u v e ( g ) ，显然有c ( u ) nc ( v ) = ，所以c 就是g 的 一个n ：b 染色即) ( ，( g ) i n f a b i g 存在a ：6 染色) 综上所述，) ( ，( g ) = i n f a b l g 存在a ：6 染色) 定理1 1 说明了定义13 与定义1 1 是等价的并且只要我们能够构造出图g 的一个 n ：b 染色，就能给出它的分数色数的一个下界 在这一部分的内容行将结束之前，作为准备，我们依次列出下文中将要用到的三个著 名定理：b r o o k s 定理，四色定理和g r s t z s c h 定理定理1 2 中的a ( c ) 表示图g 的最大度 4 l 图的分数染色的三种等价定义及其性质 定理1 2 9 】若g 是连通的简单图，且g 既不是完全图，也不是奇圈，则x ( e ) ( g ) 定理1 3 h 若g 是平面图，则x ( g ) 4 定理1 4 设g 是平面图，若g 的围长g ( e ) 4 ，则x ( c ) 3 5 5 2 一类4 一正则循环图的分数色数 2一类4 一正则循环图的分数色数 在这一节中主要应用了分数染色的第一种定义以及相应的性质来讨论了邻接矩阵第 一行分别为 0 1 1 0 0 0 0 1 1 和 0 1 0 1 0 0 0 0 1 0 1 的n 阶4 一正则循环图的分数染色，给出 了具体的分数色数，并结合b r o o k s 定理给出了邻接矩阵第一行为 0 1 1 0 0 0 0 1 1 的n 阶 循环图当n 不是3 的倍数时的顶点色数 定义2 1 。】若一个图g 的邻接矩阵是循环矩阵，则称g 为循环图 定理2 1 川若g 是邻接矩阵一行为f 0 1 1 0 0 0 1 1 1 的n 阶循环图，则 f 3 ，n ；0 ( m o d 3 ) ； x ，( g ) = 3 n ( n 一1 ) ，n i l ( m o d 3 ) ； i3 n ( n 一2 ) ，n i2 ( m o d 3 ) ； 证明令v ( v ) 一 u l ，u 2 ，) 由图g 的邻接矩阵可知v l v 2 。 l 是一个圈，并 且每个顶点与它在圈上距离为2 的顶点相邻 1 1 当n ；0 ( r o o d 3 ) 时，令礼= 3 k ，k 矿 首先证明g 的独立数为k 我们将v 划分为k 个不交的子集，k ，k ，这里 k = f 口3 。一2 ， 3 。一。，u 3 。) ，显然k 是三个顶点的团，i = 1 ，2 ，k ，v = uk ，以下我们 构造最大独立集令尬= f 功 ；取v 6 ，它与中的顶点均不相邻，将v 6 添入 尬得到尬一 3 ，u 6 ) ；取v 9 v 3 ，它与，k 中的顶点均不相邻，将u 9 添入飓得到 慨= 3 ，v 6 ，v 9 ) ；继续这一过程，得到 矗= 杖3 ，v 6 ，u 3 ；) ；取 3 ( m ) k + 1 它与h ，k ，k 中的顶点均不相邻，将v 3 ( 州1 添入 以得到坛+ 1 = 3 ，v 6 ，u 3 ( 州) ) ； 如此f 去，这一过程在进行到第k 步时停止，得到独立集m k = 3 ，v 6 ，v 3 ) 显然 弧是g 的最大独立集，即。( g ) = k 这样由性质1 1 就可以得到x f ( g ) 3 然后给图g 构造一种分数顶点3 染色令岛= u 3 ， 6 ，v 3 ，由前面的讨论知道 s 1 是图g 的一个最大独立集，由于循环图是一个顶点对称的图，所以将s 1 中各顶点同 时按同一方向移动i 个位置( 即各顶点的下标加i ，并取模3 k ) 后得到的集合& + 1 也是 g 的最大独立集，即： s 1 = f 3 ，v 6 ，v 3 k ) ； = m ，”7 ，u 1 ) 岛= 2 ，v 5 ，v 3 k 一1 ) 6 2 一类4 一正则循环图的分数色数 显然，v v v ( a ) 恰在k 个独立集中设相对应的分数染色 ，( & ) = i ji i ：= 3 1 , 2 + , - 1 ，i ：? i ，这里f 表示g 的所有独立集的数目 从而有 ，( s ) = 1 所以这样构造的，是一个分数3 染色，即xr ( g ) 墨3 v e s i 综上所述，有骱( g ) = 3 2 ) 当礼；1 ( m o d 3 ) 时，令礼= 3 + 1 ，k z + 首先证明g 的独立数为我们将矿划分为k + 1 个不交的子集k ，k ，k “ 这里k = u 3 _ 2 ，u 3 ，v 3 i ) ，显然k 是三个项点的团，i = 1 ，2 ，七，k + l = 3 + 1 ) ，v = uk 类似于1 ) 中独立集的构造方法，可以得到独立集慨= ”3 ，”6 ，? 2 3 a 由于 v 3 k + 1 与”3 相邻，因此m k 是g 的最大独立集，即n ( g ) = k 这样由性质1 1 就可以得 至0 x s ( c ) ( 3 k + 1 ) k = 3 n ( n 一1 ) 然后给图g 构造一种分数顶点( 3 + 1 ) k 染色类似于1 ) 中的讨论，就可以得到g 的3 + 1 个最大独立集： 毋= v 6 岛= 啦，v 7 ， ，v 3 ) ； u 3 + 1 岛k + 1 = v 5 ，v 3 k 一1 ) 显然，v v v ( c ) 恰在个独立集中设相对应的分数染色 鹏) = 守= 娄0 麓+ f - 从而有丢肥) _ 1 所以这样构造的，是一个分 数( 3 女+ 1 ) k 染色，即x s ( a ) ( 3 k + 1 ) k = 3 n ( 礼一1 ) 综上所述，有x s ( c ) = 3 n ( n 一1 ) 3 ) 当礼= 2 ( m o d 3 1 时，令礼= 3 k + 2 ，k z + 首先证明g 的独立数为南我们将y 划分为+ 1 个不交的子集，k ，k ，k 十1 这里k = 3 。一2 ， 3 。一1 ，v 3 i ) ，显然k 是三个顶点的团，i = 1 ，2 ，k ，v k + l = v 3 k + ，v 3 k + 2 ，y ：廿k 类似于1 ) 中独立集的构造方法，可以得到独立集m k = u 3 ，u 6 ，v 3 k 由于u 3 k 与k + 1 ， 3 r + 2 均相邻，因此慨是g 的最大独立集，即 q ( g ) = k 由性质1 1 就可以得到x ( g ) ( 3 k + 2 ) 七= 3 n 一2 ) 然后给图g 构造一种分数顶点( 3 + 2 ) k 染色类似于1 ) 中的讨论得到g 的3 + 2 个最大独立集： 马= 3 ，v 6 ，一，u 3 k ) ； = 4 ， 7 ，v 3 k + 1 ) ； 岛k - - 2 = 2 ，v 5 ，。一， 3 1 显然，v v v ( c ) 恰在k 个独立集中设相对应的分数染色 鹏) = 孛三妄。等从而耵v 。s 。鹏，所以这样构造的馒懒 数( 3 k + 2 ) k 染色，即) c ，( g ) ( 3 k + 2 ) k = 3 札( 凡一2 ) 、 综上所述，有x s ( g ) = 3 凡( n 一2 ) 得证 推论2 1 1 若g 是邻接矩阵第一行为 0 1 1 0 0 0 1 1 的n ( 5 ) 阶循环图，则 当n o ( m o d 3 ) 时，x ( c ) = 4 证明当n 0 ( r o o d 3 ) 时，显然这样的图g 既不是完全图也不是奇圈，而且，由g 的 邻接矩阵知道z x ( c ) = 4 ，所以，由b r o o k s 定理就有x ( c ) a ( c ) = 4 又由定理2 1 知道 ) ( ，( g ) 3 ，而x ，( g ) x ( g ) ，所以3 3 ) 阶循环图，则有： ) ( r f g ) ： 2 + 当，旺1 ( r o o d 2 ) ； 一。 【2 ， n e o ( m o d 2 ) 证明令v ( c ) = 1 ，y 一，) ，由图g 的邻接矩阵可知u l u 2 v n v l 是一个圈，并 且每个顶点与它在圈上距离为3 的顶点相邻 1 ) 当礼il ( m o d 2 ) 时，由于n 3 ，所以令n = 2 k + 3 ，k z + 首先证明g 的独立数为我们将v 划分为k + 2 个不交的子集，k ，k + l ，这里 k = 现。一l ，v 2 1 ，显然k 是两个顶点的团，i = 1 ，2 ，k + 1 ，k + 2 = v 2 k + 3 ，v = uk ， 以下我们构造最大独立集取口l k ，令m x = 1 ) ；取v 3 ， 3 与虮不相邻，将v 3 添 入 矾得到 如= 1 ，v 3 ) ；取，由于v 5 仅与四个下标为偶数的顶点相邻，因而v 5 与v ，v 3 均不相邻，将添入且如得到= ”1 ，v 3 ，y 5 ；继续这过程，得到 尬= l ，v 3 ，v 21 ；取v 2 m k + 1 由于v 2 州仅与四个下标为偶数的顶点相邻，因而 地计1 与v l ，7 7 3 ，现 - l 均不相邻，将v 2 什1 添入 磊得到 正+ 1 = u l ，。3 ，v 2 1 + 1 ；如此 下去，这一过程在进行到第步时停止，得到独立集帆= 口，v 3 ，v 2 k - 1 由于k + 。 中的点v 2 k + 1 与m k 中的点u 1 相邻，”2 + 2 与 氟中的点 3 相邻，k + 2 中的点v 2 k + 3 与 靠 中的点v ，相邻，因而这样构造出来的m k 是图g 的最大独立集，即o ( g ) = 七这样由性质 1 1 就可以得到z s ( c ) 22 + ；= 2 + 忐 8 5 2 一类4 一正则循环图的分数色数 然后给图g 构造一种分数顶点2 + ；染色令岛= 1 ， 3 ，1 5 2 k1 ) ，由前面的讨论 知道是图g 的一个最大独立集，由于循环图是关于顶点对称的，所以将岛中各顶点 同时按同一方向移动i 个位置( 即各顶点的下标加1 ，并取模2 k + 3 ) 后得到的集合& + ， 也是g 的最大独立集，即： 岛= 口1 ，v 3 ，一，v 2 k 1 ) ； 岛= u 2 ，v 4 ，一，? j 2 k ，； 岛k + 3 = y 2 k + 3 ，v 2 ，地一2 显然，v vev ( c ) 恰在k 个独立集中，设相对应的分数染色 f ( s d ：i 1 ，i 2 1 ，2 ，2 2 + 3 ：，这里f 表示g 的所有独立集的数目从而有 o0 ，z = 2 k + 4 ，- 一，z ，( & ) = 1 所以这样构造的f 是一个分数2 + ；染色，即，( g ) 2 + 综上所述，有z s ( c ) = 2 + ；= 2 + 熹 2 ) 当n e l ( t o o d 2 ) 时，令n = 2 k 首先证明g 的独立数为我们将v 划分为k 个不交的子集h ，这里 k = z 一，口2 。) ，显然k 是两个顶点的团，i = 1 ，2 ，v = uk ，以下我们构造 最大独立集取t ，1 k ，令蛆= u 1 i 取口3ek ，地与口1 不相邻，将y 3 添入尬 得到= ”1 ， u 3 ；取口5 由于口5 仅与四个下标为偶数的顶点相邻，因而v s 与 l ，v 3 均不相邻，将地添入 如得到慨= u 1 ， 3 ，1 ) 5 ；继续这一过程，得到 尬： 仉， 3 ，v 2 i1 ) ；取口2 州ek + 1 由于口2 + 1 仅与四个下标为偶数的顶点相邻，因而 口2 与 1 ， 3 ， 2 。一l 均不相邻，将 2 + l 添入舰得到 五十l = u 1 ，v 3 ，v 2 i + 1 ) ；如此 下去，这一过程在进行到第步时停止，得到独立集螈= 1 ， 3 ，1 2 k - 1 显然，这样 构造出来的呱是g 的最大独立集，即( g ) = 七这样由性质1 1 就可以得到) ( ，( g ) 2 然后给图g 构造一种分数顶点2 染色令s 1 = 口- ， 。，u 。一1 ，由前面的讨论知道 岛是图g 的一个最大独立集，由于循环图是一个顶点对称的图，所以将s 1 中各顶点同 时按同一方向移动i 个位置( 即各顶点的下标加1 ，并取模n ) 后得到的集合& + 1 也是g 的最大独立集，即： s 1 = ”1 ， 3 ，- ，v 2 k - 1 ) ； 岛= u 2 ，1 1 4 ， 2 k ) 岛k = u 2 ，1 ) 2 ，一，v 2 k 一2 ) 显然，v u v ( c 卜晗在个独立集中。设相对应的分数染色 9 2 一类4 一正则循环图的分数色数 ，( s ) = i ! i i 二支辜j i ：i i ，这里z 表示g 的所有独立集的数目 从而有 ，( & ) = 1 所以这样构造的f 是。个分数2 染色，即x ，( g ) 2 综上所述，有x s ( g ) = 2 得证 1 0 ：= ： 一：一：= 。：! ：! ：= 垦三耋兰：兰! 塞：! 竺里竺坌垫塞鍪 3一类广义p e t e r s o n 图的分数色数 在文献 1 2 中给出了关于广义p e t e r s o n 图的定义：广义的p e t e r s o n 图g ( n ，k ) 是这样 一个立方图，其中n 5 ，0 k n ，顶点集和边集分别是 v = u 0 1u l ，t ) u n 一1 ，v 0 ，v l ，一，一1 ) e = ? t i t t i + l ，u i v i ，v i v i + i i 一0 ，1 一，n 一1 ， 其中下标取模m 在本文中，我们仅考虑了当= 2 时的p e t e r s o n 图，并把这类图称为一 般的p e t e r s o n 图，为了在证明过程中便于叙述，我对这类图又给出了如下的等价定义： 定义3 1 【”】给定一个圈c ，关于g 的一般p e t e r s o n 图p ( g ) 它的顶点集合y ( 曩g ) ) = v ( c ) x 1 ，2 ) 并且 1 ) ( u 、1 ) 与( u ，2 ) 之间有边； 2 ) ( ，1 ) 与，1 ) 之间有边 = 净1 ) w e ( e ) ： 3 ) ( u ，2 ) 与，2 ) 之间有边 = 寺| “y ( c ) ，使得“口e ( c ) r w u e ( e ) 定理3 1 【1 3 】设p ( g ) 是关于长为n 圈的一般p e t e r s o n 图，则 x ，( p ( o n ) ) = s n ( 3 n + 1 ) s n ( a n 一1 ) s n ( a n + 2 1 s 3 ， n i 1 ( r o o d 4 1 n ；3 ( r o o d 4 1 佗i 2 ( r o o d 4 1 礼；0 ( m o d 4 1 证明首先令圈c 乞= ”l 2 移1 1 ) 当礼；l ( r n o d 4 ) 时，令n = 4 k + 1 ，z + 由广义p e t e r s o n 图的定义知道，( v 】，1 ) ( 2 ，1 ) ( 4 k 十1 ，1 ) ( 口1 ，1 ) 构成了一个长为 4 + 1 的圈，记为c k + 1 ；( 吼，2 ) ( u 3 ，2 ) - ( 4 k + 1 ，2 ) ( 优，2 ) ( u 4 ，2 ) - ( u 4 k ，2 ) ( 1 ) 2 ) 构成了 另一个长为4 + 1 的圈，记为c 氛+ 1 首先选取c h + 1 的一个最大独立集s f = ( 吼，1 ) ，( v 3 ，1 ) ，( v 4 k 一，1 ) ) 显然i 研l = 2 k ，然后再从+ 。中选出部分顶点添入 研构成尸( g ) 的最大独立集。由于( 饥，2 ) ，( v 3 ，2 ) ，( w 4 女一1 ，2 ) 与研中对应顶点相 邻，因此满足条件的顶点仅能从c 氙+ 1 的其余顶点( v 4 + ，2 ) ，( 2 ，2 ) ，( 2 ) ，( u a k ，2 ) 中选取，而这些顶点恰好导出了一条长为2 的路、它的最大独立集研= ( 砜k 、2 ) ，( 1 4 ，2 ) ，( 1 ) 8 ，2 ) ，( v 4 k 砘2 ) ，( v 4 k ，2 ) f 研i = k + 1 这样s = s fu s f 就构成 了图p ( g ) 的最大独立集，并且o ( 曩瓯) ) = l s f u 研l = 3 女+ 1 这样，由性质1 1 就有 x ，( p ( k ) ) ( 8 k + 2 ) ( 3 七+ 1 ) = 8 n ( 3 礼+ 1 ) ，f-_l-lll，、lilll 3 一类广义p e t e s o n 图的分数色数 下面构造p ( g ) 的一个分数( 8 + 2 ) ( a k + 1 ) 染色。由刚才的讨论知道， s 1 一 ( 1 ，1 ) ，( v 3 ，1 ) ，一，( 4 k 乩1 ) ，( v 4 k 扎2 ) ，( 4 ，2 ) ，( v 4 k 幽2 ) ，； 是p ( 瓯) 的最大独立集，由广义p e t e r s o n 图的对称性知道，将岛中的个各点均同时按 同一方向移动i 个位置( 即各顶点的下标加i ，并取模4 + 1 ) 后得到的集合& + ，也是g 的最大独立集： 岛= ( 口2 ，1 ) ，( v 4 ，1 ) ，( v 4 k ，1 ) ，( v 1 ，2 ) ( v 5 ，2 ) ，( v 4 k 一2 ，2 ) ) ； & + l = ( 口4 + 1 1 ) ( v 2 ，1 ) ，- ，( y 4 k 一2 ，1 ) ，( v 4 k ，2 ) ，( v 3 ，2 ) ，( 砜d ，2 1 选取强+ l 的一个最大独立集霹= ( 叭，2 ) ，( ，2 ) ，( u a 扎2 ) ，( v 4 ，2 ) ，( ”4 女一2 ) 类似于前面的讨论，要得到图p ( g ) 的最大独立集，只要再找到q k + ，一 ( u 1 ，1 ) ，( 地，1 ) ，( v 4 + 1 ，1 ) ，( v 4 ，1 ) ，( 4 k 一4 ，1 ) ) 中的最大独立集踺 翘= ( 2 ，1 ) ，( v 6 ，1 ) ，一，( v 4 k 一2 ，1 ) ，( v 4 k ，1 ) 令& + 2 = 鹾u 鼋 & + 2 = ( l ，2 ) ，( v 5 ，2 ) ，一，( v 4 k + 1 ，2 ) ，( 4 ，2 ) ，- 一，( v 4 k 一4 ，2 ) ，( v 2 ，1 ) ，( v 4 k 一2 ，1 ) ，( v 4 k ，1 ) ) 再将k + 。中的各点同时按同一方向移动i 个位置，得到以下集合： 瓯k + 3 = ( v 2 ，2 ) ，( v 6 ，2 ) ，( 1 ，2 ) ，( 5 ，2 ) ，( m k 一3 ，2 ) ，( v 3 ，1 ) ，( v 4 k - 1 11 ) ，( v 4 k + 1 ，1 ) ； s s k + 2 = ( 4 + 1 12 ) ，( v 4 ，2 ) ，( v 4 k ，2 ) ，( v 3 ，2 ) ，( v 4 k 一5 ，2 ) ，( v l ，1 ) ，( v 4 k 一3 ，1 ) ，( v 4 k 一1 ，1 ) ) 这样就得到了图尸f g ) 的跳+ 2 个最大独立集令对应的分数染色 ，( & ) ：f 南，2 2 1 ，2 ，8 毛+ 2 ：，这里f 表示g 的所有独立集的数目 从而 o 0 ，i = 8 k + 3 ，一，f 有，( & ) = 1 所以这样构造的f 是一个分数( 8 k + 2 ) ( 3 k + 1 ) 染色，即x i ( g ) s ， ( 8 + 2 ) ( a k + 1 ) = s n ( 3 n + 1 ) 综上所述，有x ，( g ) = s n ( 3 n + 1 ) 得证 2 ) 当；3 ( r o o d 4 ) 时，令= 4 + 3 ，k z + ( v 1 ，1 ) ( u 2 ，1 ) ( u 4 k + 3 ，1 ) ( 1 ，1 ) 构成了一个长为4 七+ 3 的圈，记为四k + 3 ； ( u 1 ，2 ) ( 3 ，2 ) ( u 4 k + 3 ，2 ) ( 2 ，2 ) ( m ，2 ) ( u 4 k + 2 ，2 ) ( l ，2 ) 构成了另一个长为4 + 3 的 圈，记为强+ 。类似于1 ) 中寻找最大独立集的方法，首先选取+ 3 的一个 最大独立集毋= ( u 。，1 ) ，( 1 ) ，( v 4 + ，1 ) 显然l s l l = 2 k + 1 ，然后再找到 c 磊+ 3 一( ( 吼，2 ) ，( v 3 ，2 ) ，( 啦+ 1 ，2 ) 的最大独立集。而这个图恰好是一条长为2 k + l 的 路，它的最大独立集研= ( n 女+ 3 2 ) ，( v 4 ，2 ) ，( 8 ，2 ) ，( y 4 k 一3 ，2 ) ，( v 4 k ，2 ) ) i 研1 = k + 1 这 样s = 毋u 研就构成了图p ( g ) 的最大独立集，并且a ( p ( g ) ) = i 跚u s = 3 k + 2 这样，由性质11 就有x f ( p ( g ) ) ( 8 k + 6 ) ( 3 k + 2 ) = 8 n ( a n 一1 ) 1 2 3 一类广义p e t , e r s o n 图的分数色数 下面构造p ( g ) 的一个分数( 8 k + 6 ) ( 3 + 2 ) 染色由刚才的讨论知道， 马= ( u 1 ，1 ) ，( v 3 ，1 ) ，- - ，( v 4 k + 1 1 ) ，( v 4 k + 3 ，2 ) ，( v 4 ，2 ) ，一，( v 4 h ，2 ) ) ； 是尸( g ) 的最大独立集，类似于1 ) 中，将岛中的个各点均同时按同一方向移动i 个位 置( 即各顶点的下标加i ，并取模4 尼+ 3 后得到的集合s + 1 也是g 的最大独立集： 曼= ( 口2 ，1 ) ，( v 4 ，1 ) ，( u 4 k + 2 ，1 ) ，( u l ，2 ) ，( v 5 ，2 ) ，( v 4 k + 1 ，2 ) ； & + 3 = ( 啦k + 3 ，1 ) ，( v 2 ，1 ) ，- ，( u 4 k ，1 ) ，( u 4 k + 2 ，2 ) ，( v 3 ，2 ) ，( v 4 k 一1 ，2 ) ) ： 选取强+ 。的一个最大独立集霹= ( 2 ) ，( v 5 ，2 ) ，( u 4 k + ，2 ) ，( v 2 ，2 ) ，( v 4 k 一2 ，2 ) ) ， 类似于前面的讨论，要得到图p ( g ) 的最大独立集，只要再找到+ 。一 f ( 仉，1 ) ，( 1 ) ，( ”。k + 。，1 ) ，( v z ，1 ) ，( 4 - 2 1 ) ) 中的最大独立集岛 鹾= ( 口a ，1 ) ，( v 6 ，1 ) ，( v 4 k ，1 ) ，( v 4 k + 2 ，1 ) 令瓯k 十4 = 鹾u 母 + 4 = ( u 1 ，2 ) ，( 口5 ，2 ) ，一，( v 4 k 扎2 ) ，( v 2 ，2 ) ，( v 4 k _ 2 ) 2 ) ，( v 4 ，1 ) ，( v 4 k ，1 ) ，( v 4 k + 2 ，1 ) 再将+ 4 中的各点同时按同一方向移动i 个位置，得到以下集合 5 j + 5 = ( u 2 ，2 ) ，( u 6 ，2 ) ，- ，( v 4 k + 2 ，2 ) ，( v 3 ，2 ) ，( v 4 k l ，2 ) ，( 5 ，1 ) ， & k + 6 = ( u 4 + 3 ，2 ) ，( m ，2 ) ，( v 4 k ，2 ) ，( u 1 ，2 ) ，( m k 一3 ，2 ) ，( v 3 ，1 ) ，一，( y 4 k 一1 ，1 ) ，( v 4 k + l ，1 ) ) 这样就得到了图p ( g ) 的8 + 2 个最大独立集令对应的分数染色 ，( & ) = 絮1 i = ：1 , 8 2 , + - - 7 - ，, 8 k + ，6 ，从而有岳，( & ) = 1 所以这样构造的，是一个 分数( 8 庀+ 6 ) ( 3 k + 2 ) 染色，即x a g ) 茎( 8 k + 6 ) ( 3 k + 2 ) = 8 n ( 3 n 一1 ) 综上所述，有x r ( g ) = 8 n (