（计算数学专业论文）图与超图的全着色.pdf

重庆大学硕士学位论文中文摘要 摘要 为了恰当地表示大型超网络、数据库系统、时间安排和线路设计等研究课题中 各元素之间的关系，超图全着色理论做为一般图全着色的推广被自然的引入。由 于其良好的应用背景，超图全着色理论成为现在图论领域中迅速发展的子学科之 一，也是各学者们所热衷的研究方向。 本文首先综述了一般图中全着色的概念和研究现状，然后自然地引入了超图中 全着色的分类和概念。随后着重讨论了特殊超图，如：超星、超树等的全着色性 质。 在研究超星全着色时，阐述了超星不同的定义，对其进行了分类，并根据本文 研究的需要，采用定义3 2 为超星的概念。接着给出超星的弱全色数和强全色数表 达式，并有详细的理论性证明。再根据超星的结构特征，证明了超星全着色的计 数公式。最后提出了关于超星全着色的两个有效算法，同时通过两个例子说明了 全色数表达式、全着色计数和算法的正确性。 根据定义3 2 确定的超星是线性超树的一个特例，第四章就进一步对线性超树 进行研究，加深了第三章超星全着色的研究。在讨论超树全着色时，引入了一个 新的概念超树对应二部树。超树和其对应二部树是一一对应的，二部树能够 完全反映超树的点边邻接关系。则根据超树和其二部树的对应关系，我们将超树 全色数的求解转变成计算满足一定条件的二部树的点色数。这大大降低了计算的 复杂度。 无论是超星还是线性超树都是简单、有限的无圈超图，但超图中并不是只有无 圈的，而且圈在全着色理论中占据很重要的位置。所以，第五章讨论了两种有圈 超图的全着色。首先从一般图中轮图和扇形图的全着色入手，逐步引出超图中轮 图和扇形图的概念及全色数表达式。以上几章的讨论都是围绕着特殊超图展开的， 但特殊超图只占超图领域中很小的一部分，大多数的都是一般的，无特点的。第 六章则给出了关于n 个点m 条边的线性超图全色数的两个猜想。 在系统建立全着色理论的基础上，本文着重研究了几类特殊超图的全着色性 质。并结合实际问题的需要，给出了一般线性超图全色数的两个猜想。最后提出 关于全着色的继续研究方向：非线性超图的全色数、重图、伪图，还有现在比较 热的混合超图等。 关键词：全着色，弱全色数，强全色数，全着色计数 重庆大学硕士学位论文 英文摘要 a b s t r a c t i nm a n yp r o j e c t sl i k el a r g es u p e r - n e t w o r kr e s e a r c h , d a t a b a s es y s t e m sr a s e a r c l l ， t i m i n gr a s e a r c l l ，c i r c u i td e s i g nr a s e a r c ha n ds oo n , t h et h e o r yo ft o t a lc o l o r i n gc a n r e p r e s e n tr e l a t i o n s h i p sb e t w e e ne l e m e n t st h e r e d u et oi t sg o o da p p l i c a t i o nb a c k g r o u n d ， t o t a lc o l o r i n gt h e o r yh a sb e c o m ear a p i d l yd e v e l o p i n gs u b j e c ti nt h ef i e l do fg r a p h t h e o r ya n da l s ob e c o m eo n eo f t h eh o ts t u d i e s f i r s t l y , w es u n m n a r i z et h ec u r r e n tr e s e a r c ho nt h et o t a lc o l o r i n go fg r a p ha n d r e l a t e db a s i cc o n c e p t s ，a n di n t r o d u c et h ec a t e g o r i e sa n dc o n c e p t so ft o t a lc o l o r i n go f h y p e r g r a p h sn a t u r a l l y t h e nd i s c u s s i n gt h et o t a lc o l o r i n go fs p e c i a lh y p e r g r a p h s ，f o r e x a m p l e ：h y p e r s t a r , h y p e r t r e ea n d s oo n w ee x p a t i a t eo nt h ed i f f e r e n tc o n c e p t so fh y p e r s t a ra n dc l a s s i f yi tw h e ns t u d y i n g t h et o t a lc o l o r i n go f h y p e r s t a r t h e nb a s e do nt h en e e do f r e s e a r c l l ，w ea d o p tt h ed e f i n e 3 2a st h ec o n c e p to f h y p e r s t a r n e x tt h ee x p r e s s i o no f w e a kt o t a lc h r o m a t i cn u m b e ra n d s t r o n gt o t a lc h r o m a t i cn u m b e ri sp r e s e n t e d w i t ht h ed e t a i l e da n dr e a s o n e dp r o o t h e n b a s e do nt h es t r u c t u r a lc h a r a c t e ro fh y p e r s t a r , t h ee n u m e r a t i o nf o r m u l a r yo ft o t a l c o l o r i n gi sp r o o f e d a tl a s tt w oe f f e c t i v ea l g o r i t h m so nt o t a lc o l o r i n ga r ep r e s e n t e d t h e v a l i d i t yo ft h ee x p r e s s i o no fw e a kt o t a lc h r o m a t i cn u m b e ra n ds t r o n gt o t a lc h r o m a t i c n u m b e r , t h ee n u m e r a t i o nf o r m u l a r ya n dt h ea l g o r i t h m si sp r o o f e db yt w oe x a m p l e s t h eh y p e r s t a ri sas p e c i a lr o a lo fl i n e a rh y p e r t r e e s w ew i l ls t l l d yt h et o t a lc o l o r i n g o fl i n e a rh y p e r t r e e si nc h a p t e rf o u r w ea d o p tan e wc o n c 印t _ - m eb i t r e ec o r r e s p o n d e d t oal i n e a rh y p e r t r e e i tc a nr e f l e c tt h er e l a t i o no fv e r t i c e sa n de d g e sc o m p l e t e l y , s ot h e p r o b l e mo ft h et o t a lc h r o m a t i cn u m b e ro fl i n e a rh y p e r t r e ei sb e c o m i n gs o l v i n gt h e c h r o m a t i cn u m b e ro fb i t r e ec o r r e s p o n d e dt ot h el i n e a rh y p e r t r e e i tr e d u c e st h e d i f f i c u l t yo f t h eq u e s t i o n b o t ht h eh y p c r s t a ra n dl i n e a rh y p e r t r e ea l es i m p l e ，f i n i t ea n da c y e l i ch y p e r g r a p h , b u tt h eh y p e r g r a p hi sn o ta l la c y c l i co n e s ，m o r e o v e r , t h et o t a lc o l o r i n go fc y d ei sm o r e i m p o r t a n t i nt o t a lc o l o r i n gt h e o r y s ow er e s e a r c ht h et o t a lc o l o r i n go ft w o c y c l e - h y p e r g r a p h f i r s t ，r e s e a r c h i n gt h ew h e e la n df a ni ng r a p ht h e o r y , t h e ns t u d y i n g t h et o t a lc o l o r i n go f w h e e la n df a ni nh y p e r g r a p ht h e o r y a tl a s t , t h ee x p r e s s i o no f t o t a l c h r o m a t i cn u m b e ri sp r e s e n t e d w et a l ka b o u ts p e c i a lh y p e r g r a p h sf r o mc h a p t e rt h r e et o f i v e ，b u tal o to fh y p e r g r a p sa r eg e n e r a l l y t h e r e f o r e , t w oc o n j e c t u r e so nt h el i n e a r h y p e r g r a p ho f n v e r t i c e sa n dm e d g e sa r ep r e s e n t e d n 重庆大学硕士学位论文英文摘要 b a s e do ne s t a b l i s h i n gs y s t e m i c a l l yt o t a lc o l o r i n gt h e o r y , w ee m p h a s i z eo nt h e p r o p e r t yo ft o t a lc o l o r i n go fs o m es p e c i a lh y p e r g r a p h s c o m b i n e dw i t ht h en e e d so f p r a c t i c a lp r o b l e m ，t w oc o n j e c t u r e sa r ep r e s e n t e d f i n a l l y , w ep r o v i d et h en e w r e s e a r c h d i r e c t i o n ：t h et o t a lc o l o r i n go fn o n - l i n e a rh y p e r g r a p h , m u l t i g r a p h , p s e u d o g r a p ha n d m i x e dh y p e r g r a p h s k e y w o r d s ：t o t a lc o l o r i n g , w e a k t o t a lc h r o m a t i cn u m b e r , s t r o n gt o t a lc h r o m a t i cn u m b e r , t h ee n u m e r a t i o no f t o t a lc o l o r i n g i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庞太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名坊易鸸呼 签字日期： 2 哆年莎月，j 日 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( v 力。 ( 请只在上述一个括号内打“”) 学位论文作者签名：易硐马碍 签字日期：) 订年l 月l1 3 勺 年 抑阵孰砷 名 期 签 旧 煨 字 影 签 重庆大学硕士学位论文1 绪论 1 绪论 1 1 着色与全着色问题的提出 图论的产生和发展经历了二百多年的历史，从最初的萌芽阶段开始，多数问 题是围绕着游戏产生的，以瑞士数学家欧拉的哥尼斯堡七桥问题( 1 7 3 6 ) 为代表，他 发表的那篇关于七桥问题的论文被公认为是图论历史上的第一篇论文。第二阶段， 则出现了大量的图论问题以及一批精彩的结果，如四色问题( 1 8 5 2 ) 、h a m i l t o n 问题 ( 1 8 5 6 ) 、m e n g e r 定理( 1 9 2 7 ) 、k u r a t o w s k i ( 1 9 3 0 ) 定理和r a m s e y ( 1 9 3 0 ) 定理，并且逐步 将图论问题应用于解决其它领域中的某些难题。“i 羽( g r a p h ) ”这个词第一次出现是 在1 8 7 8 年英国的自然杂志中。1 9 3 6 年，匈牙利数学家d k s n i g 写出第一本图 论专著有限图与无限图的理论，那时图论作为数学的一个新的分支已经基本形 成。最近几十年，由于生产管理、军事、交通运输、计算机和通讯网络等方面许 多离散问题的出现，大大促进了图论的发展。进入2 0 世纪七十年代以后，特别是 大型电子计算机的出现，使得大规模问题的求解成为可能。图的理论及其在物理、 化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及 经济管理等几乎所有学科领域中各方面应用的研究都得到“爆炸性发展”1 1 1 。图的 应用之所以如此广泛，在于它可作为分析处理多种问题的一种较为理想的数学模 型，它的算法又可借助计算机实现，因而图论与计算机的相互结合，为图论研究 与应用开辟了更为广阔的前景。 图的着色理论起源于1 8 5 2 年的“四色猜想”【2 】，即：在一个平面或球面上的任 何地图能够只用四种颜色来着色，使得没有两个相邻的国家着相同的颜色。后来， 人们把国家( 和外部区域) 都看成点，当两个国家相邻时，代表这两个国家的两 个点之间就用一条线来连接。这样，“四色猜想”就转化为图论中的着色问题，即每 一个可平面图是4 可着色的。同时这也是图论着色问题中著名的“四色定理”。从 此，图着色理论的研究就一直在图理论中占有举足轻重的位置 3 1 ，其主要原因如 下：首先，图的着色理论可将一些对象按照一定的规则进行分类，在现实生活中 有着相当重要的作用，如：时间表问题、排序问题、交通状态、电路安排和贮藏 问题等都与图的着色理论密切相关；其次，图着色理论在离散数学上也居于要位， 离散数学上许多貌似无关的问题都可以转化为图着色问题，例：极图理论中的e r d s s 和s i m o n o v i t s 定理。1 9 7 6 年，美国伊利诺大学的k a p p e l 和w h a k e n 花费大量的时 间用计算机证明了数学史上悬挂多年的四色猜想；1 9 9 7 年，n e i l r o b e r t s o n 等又给出 了一个简化的计算机证明【4 】，但至今尚未有严密的理论性非计算机的证明。近几 年来，关于图着色问题的研究得到了许多有趣而实用的结果，同时又拓展出若干 重庆大学硕士学位论文1 绪论 新的着色分支。它将过去未解决的闯题转化为一个新的着色问题，使原问题变得 简单易懂、便于研究，但往往需要更多的技巧性。由此可见，图着色理论有旺盛 的生命力和广阔的发展前景。 图的全着色是对图的顶点和边同时进行着色，使得相邻或相关联的元素着不 同的颜色，也是图着色问题的一个分支。自1 9 6 5 年m b e h z a d ”和v i z i n g 【6 1 分别提 出图的全着色猜想后，全着色就在图的着色理论中变得越来越重要。目前已有从 特殊图类、平面图、围长、最大度和阶数的关系角度来研究全着色，并得出了许 多有用的结果，见文献 5 】【7 】- 【1 3 】，但完全证实全着色猜想仍然是一个未解决的问 题。在1 9 6 6 年b e r g e 首次提出“超图”一词，逐渐地着色理论被引入到超图中来，从 而超图的全着色也逐渐被人们重视。由于超图中的超边是顶点的有限集簇，所以 每条超边中所包含的顶点个数都是任意的，不好控制，因此至今也就是一些特殊 超图以及限制了超边中顶点个数的超图，如：完全r 一致超图【1 4 】和完全，部超图f 1 4 】 的有关着色的理论完善些，而其余更一般的超图着色理论的研究还在继续中。 1 2 着色问题的应用实例 着色问题是图论的重要问题之一，它产生于计算机科学，有很强的理论意义 和实际意义。目前，随着图的着色问题在现实生活中被广泛地应用，它逐渐成为 众多学者研究的重要领域之一。着色问题在生活中的应用很多，如：考场安排问 题，存储问题，时间表问题和距离约束同信道频率分配问题等。 例1 1 一学校中共有7 门功课( 代数、几何、拓扑、电子商务、算法分析、政 府经济学和人力资源管理学) 需要进行期末考试，学生选课情况如下： 表1 1 选课表 t 蚰l e1 1e l e c t i v et a b l e 学生选修的课程 田 代数、拓扑、算法分析 乙 电子商务、政府经济学 丙几何、拓扑，算法分析 丁政府经济学、人力资源管理学 戊 算法分析、政府经济学 问：该学校的期末考试最少要几天才能完成? 我们发现每个学生都选修了至少两门课程，所以不能把一个同学选修的两门 功课安排在同一个时间进行考试，否则就会出现冲突。 2 重庆大学硕士学位论文1 绪论 以每门功课为一个顶点，按照代数、几何、拓扑、电子商务、算法分析、政 府经济学和人力资源管理学的顺序分别标记为1 ，2 ，3 ，4 ，5 ，6 ，7 ，当且仅当两门功课被同 一个学生选修时，在相应的两顶点之间连一条边，得到一个图g ( 如图1 1 ) 。 3 图1 1 选课图 f i g 1 1t h eg r a p ho f e l e c t i v e 对该图的顶点进行正常的点着色，满足相邻的两点着不同的颜色，则同色的 顶点可以安排在同一天内进行考试。这样选修多门功课的学生就不会出现考试冲 突的现象。 在图1 1 中，点1 , 5 ，3 和2 ，3 ，5 分别组成两个三角形，三角形中的顶点是两两相 邻的。对三角形进行正常的点着色需要三种颜色，每个点着一种颜色，才可以满 足相邻的两点着不同的颜色。在这题中三种颜色就够了，即该学校的期末考试三 天之内就可以完成。假设三种颜色分别是红色、蓝色和黄色。具体着色情况如下： 红色= l ，2 ，6 ) ；蓝色= 1 3 ，7 ) ；黄色= 4 ，5 ) 相应地代表一天考代数、几何和政府经济学，一天考拓扑和人力资源管理学， 一天考电子商务和算法分析。当然这种着色方式并不是唯一的，我们还可以选择 其它的着色方法，例如： 红色= 1 ，2 ) ；蓝色= 3 ，6 ) ；黄色= 4 ，5 ，7 ) 一天考代数和几何，一天考拓扑和政府经济学，一天考电子商务、算法分析和人 力资源管理学。还有很多种安排方式，在这里我们就不一一列举了。 这个例子说明了，一个小小的考试按排问题都可以运用着色的知识来解决。 由此可见，着色问题的运用是多么的广泛和普遍，同时也体现了着色问题越来越 重要。 1 3 本文的研究目的和内容 1 3 1 本文的研究目的 本论文研究的目的是在一般图与超图全着色理论的基础上，结合一些国内外 的文献，将一般图中的一些特殊图形，如树形图、星形图、轮图和扇形图等引入 超图当中去。综述这些一般图中特殊图形全着色性质的同时，更着重讨论在超图 重庆大学硕士学位论文 1 绪论 概念下这些特殊图形的全着色性质。主要目的是为了将超图全着色理论与实际问 题中的超图模型结合起来。因此，我们将借助一般图全着色的一些研究方法，希 望能通过一些特殊超图的全着色研究作为桥梁，给出某种条件下一般超图全着色 的某些性质。同时，我们还希望能够结合实际问题将全着色进行一些有益的推广。 1 3 2 本文的研究内容 本文首先对国内外文献中有关全着色的定义作了一个阐述；其次，利用从特 殊到一般的方法讨论超图的全着色；最后，给出全着色一些可以继续研究的方向。 图1 2 直观地反映了本文各章节之间的关系： 图1 2 论文结构 f i g 1 2t h es t r u c t u r eo f t h i sp a p e r 第一章绪论。阐述着色与全着色问题的提出与应用实例，介绍了现在比较热 门的全着色研究方向和研究方法。展示了本文的研究目的与研究内容。 第二章全着色的概念与研究现状。首先简单介绍了一般图全着色的基本概 念，并阐述了现在的一些研究状况，列举了一些相关结论。其次给出了超图中全 着色的分类，以及弱全着色和强全着色的定义，着重介绍了超图全着色的发展历 程和重要结论。 第三章星形图的全着色研究。这一章是本论文的第一个重要部分。本章主要 分为两个部分超星的全着色和全着色计数。第一部分首先从一般图中星的定 义入手，引出超图中星的定义。并且针对超星的不同定义，对其进行了分类。同 时根据研究的要求，采用定义3 2 为本文中超星的定义。其次给出了在弱全着色和 强全着色下星的全色数，并给出理论性的证明。第二部分也是先从一般图中星的 全着色计数引出超星的全着色计数，并给出具体的计数表达式。由于超图的全着 色分为弱全着色和强全着色两种情况，所以超星的全着色计数也分成弱全着色计 4 重庆大学硕士学位论文 l 绪论 数和强全着色计数两类。然后根据计数时遵循的规律，分别给出两个计数的有效 算法。最后利用两个例子，说明全色数公式和算法的正确性。 第四章线性超树的全着色研究。第三章中讨论的超星是线性超树的一个特 例，本章就讨论线性超树的全着色，是第三章的一个深入。首先介绍了超树的概 念，同时引入了一个超树对应二部树的概念。超树与其对应二部树是一一对应的， 并且该二部树可以完全反映超树中点边的邻接关系，甚至是边和点的度数。在讨 论超树全着色时，就转变为讨论其对应二部树的点着色。这样就将复杂的超图的 全着色转变为满足一定条件下一般图的点着色，大大降低了研究和计算的难度。 第五章轮图和扇形图的全着色。这一章是本文的第二个重要部分。前两章都 是讨论简单、有限、无圈超图的全着色性质。在一般图中圈的着色是很重要的。 因此，本章就讨论有圈超图轮和扇的全着色，拓展了前两章的研究。本章首 先介绍了一般图中轮和扇的定义，以及一些研究现状。将一般图中轮的定义推广 到超图中，得到超图中线性轮图的定义，又在超图中轮图的基础上给出扇形图的 定义。其次根据超星全着色的特点，再结合圈的全着色给出轮图和扇形图的弱全 色数和强全色数。 第六章关于n 个点m 条边线性图全色数的猜想。第三至第五章都是在讨论特 殊超图的全着色性质。一个给定的图，知道其具体的点边邻接关系。对于特殊超 图知道的条件会更多。但超图中这种特殊图形只是很少的一部分，大部分图形都 是一般的图形，甚至还有重图和伪图等。这类图形的全着色才真正是以后研究的 重点。本章就针对含i i 个顶点m 条边的线性图形，给出关于全色数的猜想。同时 也体现了本文从特殊到一般的研究思路。 第七章结论与展望。在这里对文章中所得出的结论作了系统的概述，并提出 了关于全着色方面以后的研究工作中可以继续的一些课题。 本文讨论的图都是有限、无向、连通、非空、无环简单图。设g 是一个图， 分别用矿( g ) 、西( g ) 、( g ) 和艿( g ) 表示g 的顶点集、边集、最大度和最小度，在 不引起混淆的情况下，分别简记为取e 、和6 。本文未定义的术语和记号见参考 文献 1 5 1 6 1 。 重庆大学硕士学位论文2 全着色的概念与研究现状 2 全着色的概念与研究现状 2 1 一般图全着色的定义与研究现状 简单地说，图的全着色指在满足一定条件的情况下，既对顶点着色，也对边 着色。因此，图全着色的研究要涉及到顶点着色和边着色。而超图的全着色可以 看作是一般图全着色的一种推广。所以，了解一般图全着色的定义与研究现状对 于超图全着色的研究是非常有益的。 定义2 i t l 7 1 图g 的点着色( v e r t e xc o l o r i n g ) 是映射 妒：v ( 6 3 一 l ，2 ，k 使得任意相邻的两顶点之间着不同的颜色。满足条件的k 称为图g 的点色数 ( c h r o m a t i cn u m b e r ) ，简称为色数，记为z ( c ) 。 定义2 2 【1 刀图g 的边着( e d g ec o l o r i n g ) 是映射 妒：e ( 6 3 _ l ，2 ，k 使得任何相邻的两条边之间着不同的颜色。满足条件的k 称为图g 的边色数 ( t h e c h r o m a t i cn u m b e ro f e d g e s ) ，记为z 。( g ) 。 定义2 3 【1 7 1 图g 的全着色( t o t a lc o l o r i n g ) 是映射 妒：v ( 6 3 u e ( g ) 专 1 ，2 ，k 使得相邻或相关联的两元素间着不同的颜色。满足条件的k 称为图g 的全色数 ( t o t a l c h r o m a t i c n u m b e r ) ，记为新( 6 3 。 由全着色的概念可以直接得知，舫( g ) ( g + 1 是显然成立的。在1 9 6 5 年， b e h z a d 【5 】和比啦g 【6 】分别独立得提出了著名的全着色猜想： ( g ) + 1 z r ( g ) ( g ) + 2 文献【9 】系统综述了一般图的全着色进展，提出了研究全着色的几种方法，如：穷 着色法、转化为图的边着色法等。早期人们证明了全着色猜想对于某些特殊图形 是成立的，比如：树丁、圈e 、星g ( v ) 、完全图k 。、完全二部图k 。、完全 三部图k 。，嗍等。随着着色问题研究的深入，人们引进了关于全色数分类的概念： 口= g l 所( g ) = ( g ) + 1 ) ，c ；= g 协( g ) = a ( 6 3 + 2 j 若图g c ；，则称g 为第一类图( t y p e l ) ，若图g c ；，称图g 为第二类图 ( t y p e 2 ) 。 事实上对于一般图的全色数还是无法完全确定的，只是在某些限制下进行一 些探讨，例如对最大度作一定的限制。现在主要是分成高度图和低度图两个方面 研究。r o s e n f e l d 1 9 l 和俐o ，口明研究了低度图的全着色，他们分别独立地得到下 述结果： 6 重庆大学硕士学位论文2 全着色的概念与研究现状 设g 为简单图，如果a ( g ) 3 ，则所( g ) a ( g ) + 2 。 1 9 7 7 年时，k o s t o c h k a 把这个结论向前推进一步，得到一个更好的结果： 对任意重图g ，如果a ( g ) = 4 ，则筋( g ) 6 = ( g ) + 2 。 随后，又有数学家证明了，当( g ) s 5 时，全着色猜想也是成立的 2 0 1 。 简单图是重数为1 的图，是一种特殊的重图，因此这就证明了当最大度s 5 时， 全着色猜想对于低度图是成立的。 相对于低度图来说，高度图的结论就丰富些。 平面图除了a c g ) = 6 的情况，其余情况均已得证。r o s e n f e l d 【1 明和r i j a y d i t y a 7 】 给出了a ( g ) = 3 的证明，k o s t o c h k a 【2 i 】【2 2 1 给出当a ( g ) 5 情形的证明，而b o r o d i n 【1 1 】 和s a n d e r s 幽1 则分别证明了当( g ) 2 9 和a ( a ) = 7 时的平面图对全着色猜想也是 成立的。尤其是当( g ) 妄i 矿( g ) l 和( g ) p ( g ) 卜5 时，文献 2 4 【2 5 】给出了证明 h i l t o n 和y a p 等数学家都为高度图全着色的研究做出了巨大的贡献。c h e w 【1 2 】闭 和谢德政口7 】【2 8 】分别从奇阶和偶阶高度图两个方面，把他们的结果进行了推广。近 几年来，关于图的全着色问题的研究得到了很多有趣而实用的结果，同时也扩展 出一些新的分支，如：邻点可区别全着色 4 0 , 4 4 1 、均匀全着色【4 2 习和分数全着色 4 5 1 等。但相关结论多数是围绕一些特殊图形的，如完全图、二部图、圈、轮图、扇 形图和风车图等。 定理2 1 4 0 c n 表示 阶圈，n 4 ，则( e ) = 4 。 定理2 2 4 0 设k 。表示n 阶完全图，以3 ，则 “驴髓：篇豸 定理2 3 对于n + l 阶的扇只，甩3 ，有z 。( e ) = 5 ，z 。( f 0 = n + l ， 4 ) 。 定理2 4 4 0 1 对t - n + l 阶的轮呒，九4 ，z 。( 呒) = n + l 。 定理2 5 【4 0 对于完全二部图k 。( m 总1 ) 有 f 肌+ l ，h n + l z 。( k m ，) = 3 柳= n = 1 【玎+ 2 m = 栉2 定理2 6 4 4 对于次完全二部图g ：。，有 蹦g o = ：；所r e = n ； 定理2 7 对于烟花图“，有z 。( 巧) = 后+ 4 ( n 3 ) 。 定理2 8 4 y l 设e 表示n 阶圈，k 为正整数，则 7 重庆大学硕士学位论文 2 全着色的概念与研究现状 z ：( g ) = 3n = 3 七 3 + 三月：3 k + 1 k 3 + 上万：3 k + 2 2 | + 1 定理2 一对于完全弘叫( 驴鬣。 定理2 1 0 4 5 1 对于完全二部图k 。一 办戤户z 亿护 咎川卜1 = 定理2 1 1 4 3 设g 为o - 图，则拼( g ) = 4 。 定理2 1 2 4 3 1 对于完全二部图k 。，孵( 足。) - - - - m a x n ，n ) + 1 + j ( 所，1 ) ，其中 a ( m ，功是k r o n e c k e r 函数。 定理2 1 3 1 4 2 1 对于树r ，有 f 2t = k 2 2 h 降 + 1 a c 叫n 朋d ：陴1 + 定理2 1 4 1 4 2 1 对于圈e ( 甩3 ) ，则 陲+ 2 以；o ( m o d 2 ) 卜1 盘+ 2 甩；1 ( m o d 2 ) 陲+ 2 n ；o ( m o d 2 ) 瞩卜1 草獭d 2 ) 定理2 1 5 m 1 设g 为轮图，其中p = i 卅，则 当p 5 时，z ，( g ) = p 糖s 时( g ) _ 鬻端凌2 p - 咖2 - = o ( 删m o d 3 ) ，) 定理2 1 6 m 1 设g 为扇图g ( p 6 ) ，其中p = l 卅，则 z ，( g ) = p 一1 ，z y ( g ) = p + l 。 定理2 1 7 【3 9 1 对于圈e ，有 8 重庆大学硕士学位论文2 全着色的概念与研究现状 1 3 2 n 2 0 ( m o d 3 ) z f ( q ) = 42 n 0 ( r o o d 3 ) ，摊5 【5 n = 5 定理2 1 8 蚓对于完全图k 。，有 麒= 尝嚣 定理2 1 9 0 9 1 对于完全二部图k 。，有 z t ( x 。) = m + n ， m + n 3 定理2 2 0 t 3 9 1 对于0 一图g ，则有 z 7 ( g ) ： ：p ：_ p ，5 ，2 1 2 3 p o t n e r w l s e 以上定理是近l o 年来，关于邻点可区别全染色、分数全染色、均匀全染色和 点强全染色【”4 卿的一些研究结果。首先从数量上可以看出，这几种全着色的分支 有了很大的发展，得到不少新的结论；其次从定理的内容上看，多数都是围绕讨 论特殊图形，如：完全图、完全二部图、烟花图、0 一图、轮和扇等。可见，在特 殊图形方面还有很大的发展前景。 随着一般图全着色理论的逐渐完善，人们开始研究图的全着色的计数，文献 2 9 】 就着重研究了路、星、长为3 k 的圈以及树等特殊图形的全着色的计数。 2 2 超图全着色的概念与研究现状 超图的全着色是一般图全着色的一种推广，因此一般图着色的某些结论可以 推广到超图中来。由于超图中的超边是顶点的有限集簇，所以每条超边中所包含 的顶点个数是不定的。因此，超图的全着色就与一般图全着色概念不太一样。了 解超图点着色和边着色的定义对更好的理解全着色的概念是有益的。 定义2 4 【1 4 1 超图h 的弱点k 着色( w e s kk c o l o r i n g ) 是指对矿( 日) 的一个k 分划( 巧，k ，以) ，使得日的每条非环的边不是单色的。使超图日有弱点k 着色的 最小正整数k 称为日的弱点色数( w e a k c h r o m a t i c n u m b e r ) ，记为z ”( 日) 。 定义2 5 d 4 超图日的强点k 着色( s t r o n gk c o l o r i n g ) 是指对v ( h ) 的一个 k 分划( k ，匕，圪) ，使得日的每条边中不会出现两个着相同颜色的点。使超图日 有强点k 着色的最小正整数k 称为日的强点色数( s t r o n g c h r o m a t i cn u m b e r ) ，记 为z ( 日) 。 定义2 6 【1 4 】超图日的弱边k 着色( w e a kk c o l o r i n go fe d g e s ) 是指对 z ( h ) 的一个k 分划( 巨，e ：，b ) ，使得对任意点 ，d 。( v ) 1 ，星日( 至少包含两 种颜色。使超图日有弱边k 着色的最小正整数_ | 称为日的弱边色数 9 重庆大学硕士学位论文 2 全着色的概念与研究现状 ( w e a k c h r o m a t i cn u m b e r o fe d g e s ) ，记为z 。( 日) 。 定义2 7 【1 4 】超图日的强边k 着色( s t r o n gk c o l o r i n go fe d g e s ) 是指对 e ( h ) 的一个k 分划旧，e 2 ，晟) ，使得对任意点v ，d n ( v ) l ，星日( v ) 的边两两不 同色。使超图日有强边k 着色的最小正整数k 称为日的强边色数 ( s t r o n g c h r o m a t i cn u m b e r o fe d g e s ) ，记为z 。( 日) 。 由一般图全着色的定义可以知道，全着色是同时对顶点和边进行着色，而 超图中每条超边都是顶点的一个集簇，由于顶点个数的不确定，因此对于超图全 着色中顶点的着色就出现了不同的要求，进而就分为弱全着色和强全着色两种。 定义2 8 【1 4 】超图日的弱全着色( w e a kt o t a lc o l o r i n 9 1 是映射 伊：h u e ( h ) 一 12 ，k 使得点是弱点着色而边是强边着色，并且任意的v v ( h ) ，v e l ，e l e ( h ) ，则有 妒( v ) 妒( 层) 。使超图日存在弱全着色的最小正整数k 称为日的弱全色数 ( w e a k t o t a lc h r o m a t i c n u m b e r ) ，记为x r ( h ) 。 定义2 9 【1 4 】超图的强全着色( s t r o n g t o t a l c o l o r i n g ) 是映射 尹：矿( 日) u e ( 日) 哼 1 ，2 ，k 使得点是强点着色，边是强边着色，并且任意的v v ( h ) ，e ，e l e ( h ) ，则有 妒( v ) 伊( e i ) 。使超图日存在强全着色的最小正整数k 称为日的强全色数 ( s t r o n g t o t a lc h r o m a t i c n u m b e r ) ，记为拼( 。 也正是由于每条超边中所包含的顶点个数的任意性，以及任意两条相邻超边 公共点个数的任意性，导致了关于一般超图全着色的结论很少。但像完全，一致 超图和完全，部超图这类限制了超边中顶点个数的超图，全着色的相关结论就比较 完善，如下： 厂1 定理2 2 1 1 4 1 设月，是整数，并且2 ，h ，则z ( ) = i 三i ，z ( ) = 栉。 i ，一i l 定理2 2 2 【1 4 】若，2 ，玛，n 2 ，n ，l ，并且啊茎n 2 n ，则 定理2 2 3 【1 4 1 定理2 2 4 3 0 l 定理2 2 5 3 l 】 z c k ：，= f c ：【詈j “1 ，若z 1 c 置：，= c k ：，当且仅当，i n 。 麒翰= i ：i l l 卅+ 2 , n 一 o ( r e 。d r ) 1 0 重庆大学硕士学位论文2 全着色的概念与研究现状 忙一ji + r , n ；0 ( m 。d ，) 拼晖。2 黼。1 卜， 定理2 2 6 3 川p 1 1 若，2 , n l ，栉2 ，l ，l , 并g n ls 斗2 万，则 当，l l a 。 综上：z 罗( s 扣) ) = a + i 。 定理3 4 设s ( v ) 是阶为n ( n 3 ) 的星， 强全色数z ；( s ( v ) ) = + 1 其边集合e ( s ( v ) ) = 局，最，既) 则 a m 。a 。x e i l ) m 。a ；x 。e + 1 。 所以，当雹警 e i ) 时，z ；( s ( v ) ) = a + i 。 当 m 。 所以，当 m 。a 。x e ij ) 。 盟例+ 1 m 。a 。x e , 。 3 3 2 星形图全着色的计数 定理3 5 诌t s ( o 是阶为n ( n 3 ) 的星，则使用a + 1 种颜色所有不同的弱全着 a 色方式是，( s ( v ) ) = ( + 1 ) ! 兀( 分。1 1 ) 。 i = l 其中= 恢i ，易e ( s ( v ”，i = l ，2 ，a 。 证明： 重庆大学硕士学位论文3 星形图的全着色研究 首先，考虑对中心点v 和与其关联的超边进行着色，由于z 罗( s ( v ) ) = a + i ，中 心点v 就有+ 1 种颜色可以选择，与中心点相关联的超边依次有，a 一1 ，1 种颜 色可以选择，则第一步共有( + 1 ) ! 种着色方式。其次，再考虑每条超边中其余点 的着色。对于超边e 中的点而言，着色又分两步： 第一步，剩余的 - 1 个点在c 妒( v ) 中任选一种颜色，共有肿- 1 种选择方式； 第二步，除去所有点都与中心点选择了同一种颜色的情况，舻一1 。 因此，超边e 中点的着色方式共有舻- 1 一1 种。 同理考虑超边最，e 3 ，e a 中点的着色方式，得到星弱全着色的计数公式 n w ( s ( v ) ) = ( + 1 ) ! 兀( ，4 1 ) 。 酉 定理3 6 设s ( v ) 是阶为n ( n 3 ) 的星，则使用m + 1 种颜色所有不同的强全 a 着色方式是n s ( s ( v ) ) = p a ：l i i 璐i i 。 l f f i l 其中m = m a x 锄，) ，川= m a x 饥，i = 1 , 2 ，) ，= 旧i ，层e ( s ( v ) ) ，i = 1 , 2 ，a 。 证明： 由于z ；( s ( v ) ) = m4 - 1