（运筹学与控制论专业论文）三类特殊图的圈色数.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 图g 的星色数妒( g ) ( 亦称圈色数) ，是g 的色数x ( a ) 的个自然推广， 它最早由v i n c e 在文献f 1 1 中提出对两个整数k 和d ，若1 墨k d ，图g 的( k ，d ) 一着色定义为映射c ：v ( a ) 一 o ，1 ，2 ，k 一1 ，使得当x y e ( g ) 时，有ds o ( x ) 一c ( 可) isk d 成立一个图g 的星色数x 丰( g ) = o n ， ；：g 存在一个( k ，d ) 一着色且2 d k i v ( g ) 限此后，朱绪鼎在文献【3 中给出了 它的一个等价定义一圈色数为统一起见，本文统一称为圈色数 本文研究了平面图、m y c i e l s k i 图和距离图这三类特殊图的圈色数本文 一共分为五个部分，第一部分为引畜，介绍了圈色数的定义及其等价定义， 还总结了后面常会引用的定理和结论第二、三、四部分分别总结了关于平面 图、m y c i e l s k i 图和距离图的圈色数的一些结论和这些问题的进展情况其中 第二部分在总结平面图的圈色数已有结论的基础上，还构造了一些新的圈色 数为3 或4 的平面图第五部分为展望，总结了关于这三类特殊图的圈色数的 一些还未解决的问题 关键词：圈色数；色数；平面图；轮图；m y c i e l s k i 图；距离图 硕士学位论文 m a s t e r st h e s i s a b s t r a c t t h es t a rc h r o m a t i cn u m b e rx + ( g ) o fa g r a p hg ( s o m e t i m e si t i sa l s oc a l l e d c i r c u l a rc h r o m a t i cn u m b e r ) ( c ( g ) ) i san a t u r a lg e n e r a t i o no ft h ec h r o m a t i c n u m b e rx ( a ) o fag r a p h i tw a sf i r s td e f i n e db yv i n c ei n ( 1 1 f o rt w oi n t e g e r s 1 d k , a ( 七，d ) 一c o l o r i n go fag r a p hg i sac o l o r i n gco ft h ev e r t i c e sgw i t h c o l o r s o ，l ，2 ，七一1 s u c h t h a t ( 。，y ) e ( c ) 号d l c ( x ) 一c ( ) lsk - d t h e s t a rc h r o m a t i cn u m b e ri sd e f i n e da sx c ( g ) = 打z ， l ：t h e r ei s n ( k ，d ) 一 c o l o r i n go fga n d2 d k i y ( g ) l a f t e rt h i s ，x z h ug a v ei ta n o t h e re q u a l d e f i n i t i o n - c i c u l a rc h r o m a t i cn u m b e ri n 【3 】f o ro n e n e s s l n t h i sp a p e rc a l l si t c i c u l a rc h r o m a t i cn u m b e r i nt h i sp a p e rw ed i s c u s st h ec i r c u l a rc h r o m a t i cn u m b e ro fp l a n a rg r a p h s ， m y c i e l s k ig r a p h sa n dd i s t a n c eg r a p h s t l l i 8p a p e ri n c l u d e sf i v ep a r t s p a r t o n ei sa ni n t r o d u c t i o nw h i c hi n t r o d u c e st h ed e f i n i t i o no ft h ec i r c u l a rc h r o m a t i c n u m b e ra n di t se q u a ld e f i n i t i o n a n dt h e ni tp r e s e n t st h e o r i e sa n dc o n c l u s i o n s c i t e di a t e r p a r tt w o ，t h r e ea n df o u rh a v em a d ec o n c l u s i o n sa n de v o l u t i o n s a b o u tt h ec i r c u l a rc h r o m a t i cn u m b e ro fp l a n a rg r a p h s ，m y c i e l s k ig r a p h sa n d d i s t a n c eg r a p h s s p e c i a l l y , w ec o n s t r u c ts o m en e wk i n d so fp l a n a rg r a p h sw i t h c i r c u l a rc h r o m a t i cn u m b e r3o r4 b a s e d0 nt h et 、e s u l t sw h i c hh a v eb e e ns u r v e y e d i np a r tt w o p a r tf i v ei sa p r o s p e c t ，w h i c hs u r v e y ss o m eo p e nq u e s t i o n sa b o u t t h ec i r c u l a rc h r o m a t i cn u m b e ro ft h e s et h r e ek i n d so fs p e c i a lg r a p h s k e yw o r d s ：c i r c u l a rc h r o m a t i cn u m b e r ，c h r o m a t i cn u m b e r ，p l a n a rg r a p h ， w h e e l ，m y e i e l s k ig r a p h ，d i s t a n c eg r a p h i i 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均己在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 艰磕鞋日期：箩年6 月t 1 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即；学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 作者签名：i 祝毛 日期坷年 1 日 导师签名：专弗赴 日瓤如矿6 月f7 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本 人的学位论文提交! c a l i s 高校学位论文全文数据库”中全文发布，并可按“章 程”中的规定享受相关权益。回童途塞坦窑压澄蜃! 旦圭生；旦= 生j 旦三生 筮壶! 作者签名：k 唾 日期岖年月1 1 日 导师签名：耆节啦 日觏埘年月，e l 硕士学位论文 m a s l e r st h e s i s 第一章引言 一个图的星色数是图的色数的一个自然推广，它最早由v i n c e 在文献 1 i 中提出对两个整数k 和d ，若15k d ，图g 的( k ，d ) 一着色定义为映射 c ：y ( c ) 一+ o ，1 ，2 ，一1 ，使得当x y e ( c ) 时，有dsl c ( 茁) 一c ( 可) is k d 成立我们可以看出，对任意整数k ，一个图g 的一个( k ，1 ) 一着色其 实就是g 的一个普通虹着色，一个图g 的星色数x + ( g ) = i n ， ：g 存在 一个( k ，d ) 一着色且2 d 墨k i v ( g ) m 由v i n c e 对星色数的定义可以看出， x + ( g ) 为一个有理数星色数的另一个等价定义一圈色数由朱绪鼎在文献1 3 中给出首先他给出了r 一圈着色的定义，令e 为欧几里德长度为r 的圈，图 g 的一个r 一圈着色定义为映射c ：x ( x y ( g ) ) + e 的一段开单位弧c ( z ) 使得对g 的每条边( z ，可) ，有c ( x ) nc ( ) = 0 成立如果g 存在一个r 一圈着 色，则我们就说g 是可以r 一圈着色的文献【3 中用x c ( g ) 表示g 的圈色 数，其中x 。( g ) = i n f r ：g 可以r 一圈着色) 为统一起见，本文统称为圈色 数，用x 。( g ) 表示 在文献f 3 1 对圈色数的定义中，我们可以在圈g 的任意一点处断开圈e ， 从而得到一个长为r 的区间，把它表示为区间o ，r ) 对g 的每段开单位弧 c ( z ) ，令c ( 茁) 为c ( z ) 的起麒其中c ( 石) 是以圈g 的顺时针方向为方向的) 此时 可得映射d ：v ( c ) 一【0 ，r ) ，它满足v x y e ( g ) ，有t l c t ( 茁) 一c j ( 纠) i r 一1 从映射c 得到映射c 的过程是可逆的，因此，我们由映射c ，：y ( c ) 一f 0 ，r ) ( 它满足v x y e ( g ) ，有1 i d ( x ) 一c i ( g ) l r 一1 ) 可以确定图g 的一个 r 一圈着色 下面我幻来看这两个定义为什么等价：设c 为g 的一个( 七，d ) 一着色，令 c 为v ( c ) 一 o ，) 的映射，其中一( 茁) = 掣，则对g 的每条边( ，y ) ，都 有1 fc p ( z ) 一( ) f 一1 成立因此g 的一个( k ，d ) 一着色就对应g 的一 个一圈着色，另一方面，如果c 为g 的一个一圈着色( c 为v ( a ) 到【0 ，r ) 的一个映射) ，则c ( z ) = f ( 石) d j 即为g 的一个( 自，d ) ，着色，于是g 的一个 一圈着色也对应着g 的一个( k ，d ) 一着色所以以上两个定义是等价的 硕士学位论文 m a s t e r st h e s i s 在后面的内容中，下面的引理会用到，它由g u i c h a r d 在文献 5 5 中证明 在这个引理之前，我们先看一个定义令c 为图g 的一个r 一圈着色，按 如下方式定义一个有向图d = d c ( g ) ：其点集为v ( d ) = y ( g ) 芦到的有 向边存在当且仅当( x ，v ) e ( c ) 且c ( y ) 的左端点等于c ( x ) 的右端点，其中 区间c ( ) 的方向与顺时针方向一致，c ( v ) 的左( 右) 端点为c ( 口) 的起( 终) 点。 引理1 1 1 ( 【5 ) 设g 是一个有限图，c 为g 的一个r - 圈着色如果 d 。( g ) 中无圈，则g 有一个r 一圈着色c ，其中r 7 r ，且d e , ( g ) 中含一 个有向圈 用这个定理，朱绪鼎在文献 3 中证明了他定义的图的圈色数也是有理 数 引理1 1 1 的逆也是正确的，即下面的引理，在文献【3 中给出 引理1 1 2 ( 【3 】) 如果g 可r 圈着色，对g 的每个r 一圈着色c ，若_ d 。) 含一个有向圈，则x c ( g ) = r 因此，一个图g 的圈色数x c ( g ) = r 当且仅当 g 可r - 圈着色，且对g 的每个r 一圈着色c ，d 。( g ) 含一个有向圈 对g 的一个( p ，q ) 一着色，我们定义d $ ( g ) 为一个有向图，它的点集为 v ( a ) ，( z ，) 为d ( g ) 的有向边当且仅当( z ，y ) e ( a ) 且( ) 一咖( z ) 兰 q ( m o d p ) 风( g ) 类似于d c ( g ) 的构成，因此它们具有相似的性质，特别地， 引理1 1 2 对0 ( g ) 也成立，即以下引理，在文献 5 中有证明 引理1 1 3 ( 5 ) 对一个图g ，x c ( g ) = ；当且仅当g 可( p 口) 一着色 且对g 的任何( p ：g ) 一着色，( g ) 都含一个有向圈 引理1 1 2 和引理1 1 3 对决定一个图g 的圈着色数非常有用 由朱绪鼎在文献 3 中对圈色数的定义我们可以看出如果x 。( g ) = r ， 则对任意r 7 r ，有g 是可以r 7 一圈着色的另外当h 为g 的子图时，有 x 。( h ) s ) ( 。( g ) 成立 2 硕士学位论文 m a s t e r s1 h e s l s 下面我们定义图g 的r 一区间着色，它为映射9 ：x ( x y ( g ) ) 一区间 0 ，r 的一段开单位子区间g ( x ) ，使得v x y e ( g ) ：g ( x ) n g ( y ) = 0 文献 1 2 】 中有结论：图g 的色数x ( c ) = i n f r ：g 可以r 一区间着色 类似地，图g 的一个r 一区间着色对应于一个映射f ：y ( c ) 一o ，r ) 使得对v x y v ( c ) ，有 l i ，( o ) f ( y ) l r 一1 ，且对任意x v ( c ) 有f ( x ) r - 1 因此图g 的任一 个r 一区间着色对应图g 的一个r 一圈着色，因此有x 。( g ) x ( g ) 另一方面，对 图g 的任一个r - 圈着色c ：v ( c ) 一 0 ，r ) ，令8 = m a x c ，( z ) ：z v ( g ) ) ，则 c ，可以看作是图g 的( s + 1 ) 一区间着色，由于8 r ，因此有x ( c ) 一1 ) c 。( g ) 综上，文献 1 中得出以下结论：对任意有限图g ，有x ( c ) 一1 x 。( g ) ) ( ( g ) 对于无限图的情形，以上结论仍成立，只是证明方法和有限图的情形不 一样 1 j 2 _ h 结论告诉我们在图的结构方面，x 。( g ) 比x ( e ) 包含了更多的信息 如果我们知道一个有限图的圈色数x 。( g ) ，就可以通过对x 。( g ) 取上整得到 x ( g ) ，即( g ) = x 。( g ) 另一方面，由此也可以得到两个具有相同色数的 图有可能具有不同的圈色数所以， x 。( g ) 是x ( g ) 的一个加细，x ( c ) 是 ) ( 。( g ) 的一个近似 由x ( g ) 和x c ( g ) 的以上关系，v i n c e 在文献( 1 中提出了问题：什么样 的图满足x 。( g ) = x ( g ) 这一问题在很多文献中有研究，其中文献【3 】中证明 了关于这个问题的最强结论： 定理1 1 4 ( 【3 ) 假设x ( c ) = n ，如果v ( c ) 有一个非平凡的子集( 即 a v ( v ) 且a 0 ) ，对图g 的任一个竹一着色c ，使得e 的每一个色类x 要么包含在a 中，要么与a 相交为空集，则x c ( g ) = ) ( ( g ) 由此，g o l 等在文献【4 中得出推论： 推论1 1 5 ( 4 ) 如果g 的补图不连通，则x 。( g ) = x ( g ) 这个推论的一种特殊情况是g 含一个通点( u n i v e r s a lv e r t e x ) ，即此点与 c 中的其它点均相连这种特殊情况由朱绪鼎在【3 中证明，g u i c h a r d 在 5 3 硕士学位论文 m a s t e r st h e s i s 中也有证明，即 推论1 1 6 ( 【3 ，5 】) 如果g 有一个通点，则x 。( g ) = x ( v ) 如果图g 是唯一n 一着色的，则x ( c ) = 九，则它的任一个色集可作定理 1 1 4 中的集合a ，文献【2 】中得出以下推论： 推论1 1 7 ( 【2 】) 如果g 是唯一n 一着色的，则x 。( g ) = x ( g ) b o l l o b d s 和s a u e r 在文献 2 3 中证明了结论：对任意整数n21 ：g23 ， 存在一个图g ，它的围长至少为g ，且g 是唯一n 一着色的由此，文献 2 得出如下结论： 推论1 1 8 ( 【2 ) 对任意整数n 1 , g 3 ，都存在一个最小圈长至少为g 的图g ，且x 。( g ) = x ( g ) = n 人们认识事物的客观规律是从特殊到一般因此为了更好地研究一般图 的圈色数，我们应该先研究一些特殊图的圈色数平面图、m y c i e l s k i 图和距 离图作为三类特殊图，人们对其圈色数进行了大量的研究本文总结了关于这 三类图的圈色数的结论以及一些研究动态，并在此基础上得出了一些新的结 论本文一共分为五个部分第一部分为引言，介绍了圈色数的定义以及总结 了一些后面常会用到的结论第二部分为平面图的圈色数文献2 , 3 6 ，7 9 ，1 0 中对平面图的圈色数均有研究这些研究均是基于v i n c e 在文献1 1 中提出的 三个问题： ( 1 ) 对什么样的有理数r ，相应地存在一个平面图g ，使得x 。( g ) = r ? ( 2 ) 什么样的平面图的圈色数为37 ( 3 ) 什么样的平面图的圈色数为47 其中问题( 1 ) 已完全解决，由文献 6 ，8 】的结论可知：有理数r 为一个平 面图的圈色数的充要条件是r = 1 或2sr 4 对于问题( 1 ) 和( 2 ) ，似乎很难刻画所有的圈色数为3 或4 的平面图，但 4 硕士学位论文 m a s t e r lst h e s l s 这类图的一些无限集已被构造出来 此外，对圈色数为介于2 和3 之间，圈色数为介于3 和4 之间的有理数 的平面图也有一些相应的无限集图被构造出来本文的第二部分总结了这些 关于平面图的圈色数的结论和方法第二部分一共分为四节，第一节介绍了 有理数r 可作为一个平面图的圈色数的充要条件为r = 1 或2sr 4 ；第二 节总结了已经构造出的圈色数为2 与3 之间的有理数的平面图；第三节总结 了已经构造出的圈色数为3 与4 之间的有理数的平面图；第四节总结了圈色 数为3 或4 的平面图，并在此基础上构造了另外一些圈色数为3 或4 的平面 图 在寻找任意大色数且不含三角形的图的过程中，m y c i e l s k i 在文献1 5 1 中 对已知图g 进行了一种有趣的转化：对于一个图g ，设它的点集v ( c ) = v ，边 集e ( g ) = e ，则图的m y c i e l s k i 图表示为m ( a ) ，它的点集为v u v 7 u u ) ，其 中i “= z 7 ：z y ) ，边集为e u x y 7 ：x y e u v 7 札：7 v ，点z 7 称作点 z 的同胞点( o 也被称作z 的同胞点) ，点批称作图m ( a ) 的根在不引起混淆 的情况下，我们经常用表示m ( c ) 的根当竹三2 时，n 次迭代的m y c i e l s k i 图m “( g ) = m ( m n - 1 ( g ) ) 文献【1 6 ，1 7 ，1 8 ，1 9 ，2 0 中对m y c i e l s k i 图这类特殊 图的圈色数有研究，本文的第三部分总结了m y c i e l s k i 图的星色数的研究结论 以及研究动态第三部分分为两节，第一节总结了。( m ( g ) ) x ( m ( g ) ) 的 图g ，第二节总结了x c ( m ( g ) ) = ) ( ( m ( g ) ) 的图g 本文的第四部分总结了关于距离图的圈色数的一些结论设d 为一个整数 集，距离图c ( z ，d ) 的点集为z ( z 为全体整数的集合) ，边集为 i j ：li - jl d 由于z 是固定不变的，所以我们对 dl 的大小分类总结了c ( z ，d ) 的圈色 数 问题 第五部分为展望，总结了关于这三类特殊图的圈色数的一些还未解决的 5 硕士学位论文 m a s t e r st h e s i s 第二章平面图的圈色数 2 1 可作为平面图的圈色数的有理数r v i n c e 在文献1 】1 中提出问题：对于什么样的有理数r ，相应地存在一个 平面图g ，使得) 。( g ) = r ? 由平面图的4 色定理可得，r 4 由。( g ) = m t 几 ；：g 存在一个( k d ) 一着色且2 d 曼k | y ( g ) l 可得：2 ，即r 2 另 外存在平面图g ( 即一个点) 使( g ) = 1 由以上分析可得，r 要成为一个 平面图的圈色数的必要条件为2 r 4 或r = i 以下可以证明它同时也是 充分条件这一充分条件的证明分为两个步骤：首先d m o s e r 在文献 6 中 证明了2 和3 之间的每一个有理数都可以作为某一个平面图的圈色数，此后 朱绪鼎在文献【7 中给出了一个较d m o s e r 在文献 6 中更为简单的方法； 其次朱绪鼎在文献f 8 1 中用同样的方法证明了3 和4 之间的每一个有理数也都 可以作为某一个平面图的圈色数 下面我们就来看一下这两个定理 定理2 1 1 ( 【6 ，7 】) 对于2 和3 之间的任一个有理数一都存在一个平面图 g ，使x 。( g ) = r 定理2 1 2 ( 【8 】) 对于3 和4 之间的任一个有理数一也都存在一个平面图 g ，使x 。( g ) = r 由以上可得，有理数r 可作为一个平面图的圈色数的充要条件为r = 1 或 2 0 ，有x c ( q 3 。+ 2 ) = 3 + j i b 成立 8 硕士学位论文 m a s t e r st h e s i s 定理2 3 3 ( 1 0 1 ) 对任意整数m 0 ，有x 。( q 3 一1 ) = 3 + 毫 r e e l 图日。是按如下方式构造的：在偶圈圆。= ( u o ，u ，“2 。一t ) 中加一 点口，称它为r e e l 图的中心，在u 和u 。( i h ) 之间连边，同时连接u 2 。一，和 ? a 2 i + 1 0 = 1 ，2 ，佗，乱】= u 2 n + 1 ) 对r e e l 图r 2 m ，我们有 定理2 3 4 ( 1 0 ) 对任意整数m 1 ，x 。( r 2 。+ 1 ) = 3 + 去 令w j 。+ 1 ，w 赫+ l 为两个奇轮，( a ，b ) 和( e ，d ) 分别为w 2 。+ 1 和w j 。+ 1 的 不与中，t ：- 相连的边，w 2 n + 1 和1 阿，2 。+ 1 作h a j o s 和的图凰。为：重合点a 和 点c ，去掉边( a ，b ) 和边( e ，d ) 加上边( b ，d ) 以下结论由高国刚等在文献10 1 中给出 定理2 3 5 ( 1o ) 对任意几，m 1 ，有x 。( 风，。) = ； 对于此定理的证明，李德明在文献 9 中给出了一个更为简单的证明方 法，他主要应用了g u i c h a r dd r 在文献1 5 中证明的结论；令g 为一个连通 图，) ( 。( g ) = 当且仅当对g 的任意( k ，d ) 一着色，d c ( g ) 至少包含一个有 向圈同时他推广了这一结论 令w 2 。l + 1 ，w 2 n 2 + 1 ，w j 。+ 1 为d 个奇轮，它们的中心分别为 1 ，v 2 ，v d ， w 2 n i + 1 的外圈上的点为嵋，j = 1 ，2 ，d ，i = 0 ，l ，2 ，2 n j 我们用h a j o s 和 的构造方法得到h ( n l ，n 2 ) ：重合点札5 和乱8 ，用u 表示这个新点，去掉边 u o i u 2 1 。和u 0 2 u 2 1 ，同时增加边u i 。，u 如果h ( n l ，n 2 ，) ( 其中k 三2 ) 已经构 造完毕，我们通过归纳h a j o s 和的构造法来构造h ( n l ，礼2 ，k ，n k + 1 ) ：重合 点u 和u 扩1 ，用u 表示这个新点，去掉边“6 “和u 占+ 1 u p l ，增加边u 。u p l 以下两个结论均由李德明在文献f 9 1 中得出 引理2 3 6 ( 9 】) 如果扎 = 1 ，i = 1 ，2 ，d ，则x c ( 日( 1 ，1 ，1 ) ) = 3 + ； si 理2 3 7 ( 9 】) x 。( 日( 扎1 n 2 ，他d ) ) = 3 + j 1 我们已经知道偶轮的色数和圈色数均为3 如果在构造h ( n ，n 。，n d ) 的过程中有一个偶轮，则日( 礼，n 。，凡d ) 的色数和圈色数均为3 到此为止， 9 硕士学位论文 m a s t e r st h e s i s 关于由轮图通过h a j o s 和构造而得的平面图的圈色数的问题已经全部解决 我们回过头来看一下定理2 3 1 、定理2 34 和定理2 3 8 ，他们构造出的 平面图的圈色数均为3 + ，但平面图的类型却完全不同，而且对d 的限制 也不同定理2 3 1 中要求d 为大于等于2 的整数，而且其中的图是在一个 ( 3 d + 1 ) 一圈的基础上经过简单的连边构造而得的定理2 3 4 中只要求整数 d 0 ，其中的图为三棱柱q 3 。+ 1 定理2 3 8 中也只要求整数d 0 它是由d 个奇轮通过推广h a j o s 和构造而得的图这就说明同一个有理数r 可以对应 不同的平面图的圈色数 下面我们来总结这一节的内容v i n c e 在文献1 1 中提出了问题：哪些无 限的平面图集的圈色数为介于3 和4 之间的有理数? d m o s e r 在文献f 6 】中 最早构造出了x c ( g ) = 3 + ；的平面图g ；高国光等在文献1 1o 中构造了三类 这样的无限平面图集，它们的圈色数分别为3 + b ，3 + 击，；在此基础上， 李德明在文献 9 】中通过推广h a j o s 和的构造法，也得到了一类图的圈色数为 3 + ；我们可以看出构造出的这些平面图的圈色数均在3 和；之间，而；和 4 之间还有很大的差距，也就是它们之间还有很多的有理数，于是高国光等在 文献 1 0 】中提出问题：是否存在着圈色数为；和4 之间的有理数的平面图? 2 4 圈色数为3 或4 平殛图 v i n c e 在文献【1 】中提出问题：( 1 ) 哪些平面图的圈色数为3 7 ( 2 ) 哪 些平面图的圈色数为4 7 对于这两个问题，似乎很难给所有的圈色数为3 或4 的平面图定性，但一些满足此条件的平面图集也被构造出来了本节总结了关 于这两个问题的一些结论和方法，并在此基础上构造出了一些新的圈色数为 3 或4 的平面图 显然) ( ( w j k + 1 ) = 4 由于w 2 + 1 中包含一个通点，由推论1 ，1 6 e ，s t e f f e n 等在文献 2 中得出了以下结论： 定理2 4 1 ( 2 】) 对每个整数k 1 ，有x 。( w 2 k + 1 ) = 4 1 0 硕士学位论文 m a s t e r st h e s i s 在w k 的基础上，我们构造出了另一类圈色数为4 的平面图 定理2 4 2 如果加一个点到w ；的某个三角形中，不妨设这个三角形 为c o u c 同时增加边c o v ，钍 ，u c l ，得到图g ，则x c ( g ) = 4 证明：我们对由奇轮子和偶轮子构造出来的g 分别进行正常着色后， 可以得到x ( a ) = 4 而且加一个点u 和三条边c o y ，u u ，c l v 到w k 后，札依然 为一个通点，所以x 。( g ) = x ( g ) 因此) ( 。( g ) = 4 显然，我们可以对w k 中的所有或者部分三角形中加一个点，同时按照定 理2 4 2 的方法加边，得到图g ，g 7 显然还是一个平面图，而且它的圈色数也 为4 利用上面的结论我们可以修改一下文献f 2 】中的一个结论：奇轮子是极小 的圈色数为4 的平面图把它修改为如下形式： 定理2 4 3 当lv ( c ) i 6 时，有两类平面图满足圈色数为4 且点极 小的条件一类为w 2 k + l ，另一类为由点集y ( w 2 k ) u ) 和边集e ( w 2 ) u c i v ，。 + 1 v ，删) 构成的图g 证明： 由g 的构成方式可得，g 为一个平面图，且fv ( c ) l = 2 k + 2 而iy ( w j k + 1 ) l = 2 k + 2 ，所以lv ( c ) i = iy ( w j k + 1 ) i 又由定理2 4 2 可得 x c ( g ) = 4 所以g 也为圈色数为4 且点极小的平面图 c 图l ：定理2 4 3 对应的两个图 硕士学位论文 m a s t e r st h e s i s 定理2 4 4 令k + 1 为一个奇轮子，它的外圈上的点用u 0 ，u 1 ，z 1 2 k 表 示，中心为o ，在这个圈的外面加一点札，把 u w 。) 0 = 0 ，1 ，2 ，k 一1 ) 中部分 或所有的边加到w 2 k + 1 ，得到图g ，则x 。( g ) = 4 证明：我们已经知道x ( k + ，) 一4 如果把u 和。着同样的色，则 x ( c ) = 4 因此x 。( g ) 4 又因为- + 1 是g 的一个子图，则( w j k + 1 ) x c ( g ) 又我们已经知道) ( 。( 么+ 1 ) = 4 ，所以( g ) 4 由以上可得结论成 立 以下我们来看一下圈色数为3 的平面图 我们已经知道p e t e r s e n 图p 为一个平面图，而且它满足) ( 。( p ) = x ( p ) = 3 。另外，如果一个平面图g 的色数为3 ，且它含有一个三角形，则由推论1 1 8 可得x 。( g ) = 3 因此下面我们只讨论不含三角形的平面图，以下结论见文献 2 】 定理2 4 5 ( 1 2 ) 设w 2 + 1 的中心为钆，外圈上的点为c 0 ，c ，c 2 k ， 若对每一个u 岛加上一个剖分点地( i = 0 ，1 ，2 ，2 k ) ，得到图g 2 k + 1 ，则有 x 。( g 2 b + 1 ) = 3 在这个定理的基础上，我们得到了如下的结论： 定理2 4 6 令g 2 和g 2 , + l 在某两个特殊的边重合，即g k 的一条边和 c 2 , + 1 的一条边重合供中c 2 k 和c 2 1 + 1 分别为g 2 e 和g 2 l + 1 的外圈j ，不失一 般性，我们设c z k 的边c 0 c 2 k l 和国h 】的边晶吃重合，设c 2 k 和c 2 1 + 1 的 中一。分男为“l 、“2 ，令g = ( g 2 自o c 2 1 + 1 ) + z t l z t 2 ，月i x d c - ) = 3 证明：显然g 的色数为3 因此x 。( g ) x ( g ) = 3 用反证法证明，假 设x 。( g ) 3 令g 的r 一圈着色中对应的圈为c ，其中r 3 下面考虑札1 ，2 对应的圈g 中的开单位弧c ( “，) 和c ( 铋2 ) 由于“l 让2 以g ) ，则根据圈着色 的定义我们可得c ( 札- ) nc ( u 2 ) = 0 令a 、b 为c ( u 。) 的两个端点，a 7 、b 7 为c ( u z ) 的两个端点，则有c ( q ) n c ( u 1 ) 0 ( i = 0 ，1 ，2 ，2 k 一1 ) 事实上，若 c ( q ) nc ( 1 ) = 0 ，则c ( c 。) 、c ( u 1 ) 、c ( 地) 将为c 的三段两两不相交的开单位 t 2 硕士学位论文 m a s t e r st h e s i s co ( c ；) 图2 ：定理2 , 4 6 对应的图 弧，这与g 的长度r 3 矛盾又由于c ( q ) 与c ( c i + - ) 是不交的，由此我们 可以得到c ( c i ) c ( u 1 ) ( i = 0 ，1 ，2 ，2 k 1 ) 因此c ( q ) ( i = 0 ，1 ，2 ，2 一1 ) 要么包含a 要么包含b 不失一般性，我们假设c ( c 0 ) 包含a ，则c ( c 1 ) 包含b 、 否则c ( c 0 ) nc ( c 1 ) 0 依此类推，我们可以得到c ( c 2 一，) 包含b ，类似地， 有c ( c ：) 0 = 0 ，1 ，2 ，2 f ) 要么包含o 要么包含我们假设c ( 晶) ( c ( c 2 k 一1 ) ) 包含a ，则有c ( c ；) 包含6 ，依此下去我们可以得到c ( 4 ) 包含b 7 由于 c ( 晶) ( c ( c 2 k 一1 ) ) 包含o 和b ，c ( u ，) nc ( u 2 ) = 0 ，而且c ( c 0 ) ( c ( ) ) 包含a ，则有 c ( c 叠) 包含因此c ( 吃) 和c ( 4 f - 1 ) 均含y ，这与圈着色的定义矛盾 所以。( g ) = 3 ， 定理2 4 7 令g 2 k + 1 和q 在某两个特殊的边重叠，即岛k + l 的一条边和 a 的一条边重合供中国十l 和a 分别为g 2 k + 1 和g l 的外圈j ，不妨设为 c 2 k + 1 的边q o c 2 k 和g 的边e 0 4 1 重合，我们可以得到图g ，则x 。( g ) = 3 证明； 我们已经知道x ( g 2 k 十1 ) = 3 ，x ( g z ) = 3 ，则g 的色数为3 ，因 此x c ( g ) x ( g ) = 3 由于g z k + 1 为g 的一个子图，则( g 2 k + 1 ) 曼x c ( g ) 而( g 2 女+ 1 ) = 3 ，所以地( g ) 3 而已有x 。( g ) 3 ，所以) ( 。( g ) 一3 在定理2 4 7 中，如果令g f - g 2 t + 1 ，则g 中含一个偶圈从而我们有结 论：一些含偶圈的图也满足x c ( g ) = 3 1 3 x 。( g ) = 4 x 。( g ) = 3 图3 ：用“n 一圈超边方法”构造的星色数为3 或4 的平面图 定理2 4 8 令w ( o ，a 1 ，a 2 a 3 ) 为一个中心为0 ，外圈上的点为口1 ，a 2 ，a 3 的 3 一轮子我们对o a l ，o a 2 ，o a 3 分别加两个剖分点，可得图g ，则x 。( g ) = 3 证明t对g 进行正常着色后，可以得到x ( g ) 一3 ，因此x 。( g ) x ( g ) = 3 假设g 存在个( k ，d ) 一着色，且满足2 ds 墨lv ( c ) i = 1 0 我们列出所有 可能的，不难发现最大的5 是2 我们可以证明g 不存在( 8 ，3 ) 一着色事实 上，假设g 有一个( 8 ，3 ) 一着色，则存在一个映射c ： o l ，a 2 ，a 3 一 o ，1 ，2 ，7 ) ，使得3 墨l a t a j s5 ( i = l ，2 ，3 ) 不失一般性，我们假设c ( a 1 ) = t ( t = 0 ，l ，2 ，7 ) ，则c ( 0 2 ) = t 士3 ( m o d 8 ) 或t 士4 ( r o o d 8 ) 或t 士5 ( r o o d s ) ：同样地 c ( 。3 ) 也可以取这些值但无论c ( n 2 ) ，c ( a a ) 取以上的什么值，l c ( a 2 ) 一c ( 0 3 ) i 都不可能等于3 或4 或5 ，矛盾 所以x 。( g ) = 3 利用文献1 2 中介绍的“7 1 , 一圈超边方法”，我们可以得到其它的一些圈 色数3 或4 的平面图。事实上，我们先构造一些平面3 一圈超边( 平面4 一圈 超边) ( 日；x ，y ) 使得z ，y 在日的外面如果用平面3 - 圈超边( 平面4 一圈超 边) ( 日；。，y ) 代替x 。( g ) = 3 ( x 。( g ) = 4 ) 的平面图g 中的任何一条边，得图 g 7 则x 。( g 7 ) = 3 ( ) 。( g 7 ) = 4 ) 图3 是一些根据这个方法构造出来的圈色数 1 4 硕士学位论文 m a s t e r st h e s i s 为3 或4 的平面图 1 5 硕士学位论文 m a s t e r st h e s i s 第三章m y c i e l s k i 图的圈色数 在寻找任意大色数且不含三角形的图的过程中，m y c i e l s k i 在文献15 1 中 对已知图g 进行了一种有趣的转化：对于一个图g ，假设它的点集v ( o ) = y ，边集e ( a ) = e ，则图g 的m y c i e l s k i 图表示为m ( g ) ，它的点集为 vuv 7 u “) ，其中v 7 = z ：。v ) ，边集为eu z 可：x y e ) u 9 7 札： y 7 v 7 ) ，z 点称作点z 的同胞点( 茁也被称作z 7 的同胞点) ，点“称作 图m ( g ) 的根在不引起混淆的情况下，我们经常用 i t 表示m ( g ) 的根当 n22 时，n 次迭代的m y c i e l s k i 图m ”( g ) = m ( m ”1 ( g ) ) m y c i e l s k i 在【1 5 中证明了两个结论： x ( a ) + 1 ，( 2 ) 对于je ( a ) l 1 的图g ， 为g 的团的大小 ( 1 ) 对任意图g ，有( m ( g ) ) = 有叫( m ( g ) ) = w ( a ) ，其中”( g ) m y c i e l s k i 图作为一类特殊的图，为了更好地研究一般图的圈色数，研究 m y c i e l s k i 图的圈色数显得非常必要文献f 1 6 ，1 7 ，1 8 ，1 9 ，2 0 中对此有研究，本 节总结了这方面的结论以及研究动态 3 1x 。( m ( g ) ) ( m ( g ) ) 的图g 在证明正式的结论之前，需要如下几个引理，均由g j c h a n g 等在文献 1 6 】中给出 对g 的任意真子图日，若x ( h ) x ( c ) = k ，则称g 为k 一临界它 还可定义为g 连通，且对g 的任一条边e ，有x ( a e ) x ( a ) = 矗；或g 连 通，且对g 的任一点口，有x ( a v ) x ( a ) = k 引理3 1 1 ( 【1 6 ) 如果g 中无孤立点，则有k ( m ( g ) ) 之k ( g ) + 1 如果 g 为一临界，则m ( g ) 为( + 1 ) 临界 对于此引理的后一部分，本文用与文献 1 6 中不同的方法给予了证明 1 6 硕士学位论文 m a s t e r st h e s i s 证明：由于g 连通，则m ( g ) 也连通令”为m ( g ) 的某个点，我们 分以下三种情况讨论： 当v v ( a ) 时，设c 为g 的一个( k 一1 ) 一真着色，则可按如下方 式得m ( c ) ”的一个k 一真着色c ，：当z v ( a ) v 时，c 7 ( z ) = c ( x ) ；当 z v 7 时，c 7 ( z 7 ) = 七一1 ，c ( “) = 0 当v v 时，设c 为g v 的一个( k 1 ) 一真着色，由c 可以构造出 m ( g