（运筹学与控制论专业论文）图的列表标号着色.pdf

查壹查堂堡主堂堡丝查一一 摘要 图g 的列表标号着色l 几2 2 2 ) 一l a b e l i n g ，d l ，d 2 z + 是一个从点集v ( g ) 到颜色列 表l ( 1 ) 的函数，这里的l ( v ) = l 。l 。，l 。) ，l 。是点 ；的可用的颜色列表。，是一 个正常着色，如果i f ( u ) 一，( ) l 三画，l 茎i 2d ( “，u ) = i ( “， y ( g ) ) 。如果对所 有满足l l 。i 女v ”v ( c ) ，都可以找到g 的一个正常着色，就称g 是一l ( d l ，d 2 ) c h o o s a b l e 。图的列表标号着色数a ? “如( g ) 定义为：a ? 1 , d 2 ( 6 ) = m i n kl g r a p hg i sk 一 厶( d 】，d 2 ) 一c h o o s a b l e 。图g 的列表标号着色问题来自所谓的频道分配模型：不同的电 台要使用无线频道发射信号，为了避免相互干扰，位置十分接近曲电台要使用相差足够远 的频道，位置较近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电 台互不干扰的前提下使用最少的频道资源。 本文中我们主要讨论是d 1 = 2 ，d ：= l 时的情况，在第二章中，我们给出了路p n ，树t ， 完全图的列表标号着色数，并提出了正常列表的概念。通过对路的正常列表的讨论给 出了圆仅的列表标号着色数。第三章中证明了对任意图g ，九( g ) s 2 十2 a + l ，并给出 了平面图，外平面图二部图，弦图，强弦图的五值的上界。最后我们给出了损害度的概念和 对图的列表标号着色数定义的一个修改。 关键词，频道分配问题，列表标号着色，列表标号着色数，平面图，外平面图，弦图，强弦图。 查壹查堂婴主堂堡堕查 一 一 a b s t r a c t a 厶( d 1 ，d 2 ) 一l a b c l i n g ( d 1 ，d 2 z + ) o f ag r a p hci saa s s i g n m e n t ，o fc o l o r sf r o m t h ec o l o r s l i s t f y ) 。t h ev e tl i c e so ft h eg r a p hg ，w h e r el ( v ) = 厶l j * ；) a n d k i st h ec o l e ：s l i s to fv e tr e x 玑t h i sa s s i g n m e n bfi sa c c e p t a b l ei f i 厂( 1 。) ( v ) l2 d 。，1 is2d ( u ，z ，) = i ( 扎，口v ( g ) ) i ft h e r ei sa na c c e p t a b l ea s s i g n m e n to f g r a p hg f o ra n yc o l o r s l i s tl ( v ) w h i c hh a sf l 。f a vt j v ( 6 t ) ，g r a p hgi sc a l l e d 七厶( d l ，d 2 ) 一c h o o s a b l ea ? 1 , d 2 ( g ) ，t h e1 i s t l a b e l i n g c o l o r i n gn u m b e ro fg r a p hg ，i s m i n k g r a p h gi s 一l f ( d 1 d 2 ) 一c h o o s a b l c t h ed e f i n i t i o no fa 2 ( qa r o s e f r o mt h ec h a n n e l r a d i oa s s i g n m e n tp r o b l e m s u p p o s ean u m b e ro fs t a t i o n sa r eg i v e n w eo u g h tt oa s s i g nac h a n n e lt oe a c ho ft h eg i v e ns t a t i o n ss u c ht h a tt h ei n t e r f e r e n c ei s a v o i d e di no r d e rt , er e d u c et h ei n t e r f e r e n e e ，a n yt w o v e r yc l o s e ls t a t i o n sm u s tr e c e i v e c h a n n e l sa p a r te n o u g h ，a n da n yt w o c l o s e ls t a t i o n sm u s tr e c e i v ed i f f e r e n tc h a n n e l s t h i sp a p e ri sf o c u s e do nt h ep r o b l e m so fd l = 2 ，如= li nt h e2 n dc h a p t e r ，w e s h o wt h e v a l u eo fp a t h s 最，t r e e st ，a n dc o m p l e t eg r a p h s 砥t h e n ，w eg i v et h e d e f i n i t i o no fa c c e p t a b l ec o l o r s 7 l i s ta n dd i s c u s st h ea c c e p t a b l ec o l o r s 7l i s to fp a t h sr p r o mt h e s ed i s c u s s i o n ，w ep r o v et h a t ( c 二) = 5v n23 i nt h e3 r dc h a p t e r ，w ep r o v e a f ( g ) 2 + 2 a + lv g a l s o ，t h ea 2 su p p e rb o u n d so fp l a n eg r a p h s ，o u t e r p l a n a r g r a p h s ，b i p e x t i t eg r a p h s ，d m r d a lg r a p h sa n ds t r o n g l yc h o r d a lg r a p h sa r eg i v e n k e y w o r d s ：l f ( d l ，d 2 ) 一l a b e l i n g ，l i s t l a b e h n 9 一c o l o r i n gn u m b e r ，c h a n n e l r a d i o a s s i g n m e n tp r o b l e m ，p l a n eg r a p h ，a u t e r p i a n a rg r a p h ，b i p a r t i t eg r a p h ，c h o r d a lg r a p h ， s t r o n g l y c h o r d a l9 r a p h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及i 驶得 的研究成采。尽我所知，除了文中特别加以标注和致谢的地方外，论文z 中4 i 钽 禽其他人已经发表或撰写过的研究成果，也不包含为获得东南人学或其它教f j l 构的学位或证撕f | j 使h 1 过n 0 材料。与我一同工作的同志列本研究所做的f 阡 敞均已在沦文斗j 作了明确的磁明并表示了谢意。 研究生签名：a 磋：日期：埋至：文， 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交： 他论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存沦文。 本人电予丈档的内容* ；1 纸质论文的内容相一致。除在保密期内的 杲密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。沦爻 的公卉j ( 包括刊登) 授权东南大学研究生院办理。 到究生签名： 童蒸： 导师签名 日期：知娃t v江 东南大学硕士学位论文 致谢 本论文是在我的导师宋增民教授悉心的指导和关注下完成的。在完成论文的过程 中，宋老师渊博的知识和严谨的作风使我受益良多。此外，宋老师在严格要求论文质量 的同时，给予本人无微不至的关怀和帮助，在此表示衷心的感谢! 在研究生学 - j 期间，林文松副教授，顾国华教授，殷翔老y r p ，吴建专老师等也给予我 很多教导和帮助。从他们那里我学到了很多知识，为本篇论文的完成打下了坚实的基 础。在此表示深深的谢意l 硕士学位论文 第一章 介绍 图的着色问题研究是图论研究中一个重要的分支。而图的着色有着诸多的定义，比如说顶点着 色，边着色等等。尽管定义很多，然而这些定义往往都是来自于现实的世界，是为了描述某个现实问 题而建立的抽象模型。我们提出的图的列表标号着色数也是对现实生活中所谓频道分配问题的抽象 描述 1 1 频道分配问题 h a l e 在i o 提n 的频道分配问题( r a d i o c h a n n e lf r e q u e n c ya s s i g n m e n t ) 是：讨论如何最优的在 不同的电台分配有限的频道的问题。在某一个地理区域内有多个电台，各个电台都要利用无线电波发 送自己的信号但是我们知道，如果不同的电台使用了相同的或者相近的频道时，那么就会产生相互 干扰所以各个电台都要避免使用可能产生干扰的频道。同时地理位置也会影响电台频道的分配。事 实上，如果两个电台相距的足够远，那么即使它们使用了相同的频道也不会影响其正常工作。另一方 面，地理位置接近的电台就要保证使用的频道有一定的相差，而对于地理位置十分接近的电台，仅仅不 同的频道是不够的就必颈使用相差的足够远的频道才能保证不相互干扰。将频道分配给电台，我们 的目标是在保证电台互不干扰的前提下使用最少的频道资源。 描述频道分配问题的数学模型有不少。h a l e 在【1 g 】中用图论中t c o l o r j n g 的概念来描述频道分 配问题，有关于t c o l o r i n g p j 讨论可以参阅【7 ，【8 ，i l i ，【20 ) 。r o b e r t s 在：1 2 2 9 用标号着色的概念来讨 论频道分配问题： 定义1 i 1 对于筒掌g a ( k e ) 对于任意给定的实教d 0 ，图的标号者色仁d ( 21 ) 一l a b e l i n g ) 是一 千非负函数，：v ( g ) ，0 ，o 。) 满足条佯+ ( 1 ) l ，( u ) 一f ( v ) 之2 d ，( 1 1 ，u ) e ( g ) ( 2 ) j f ( u ) 一f ( t 川d ，d ( u ， ) = 2 目g 的标号者色烈仁d ( 2 ，1 ) 一l a b e l i n gn u m b e r ) 定义为： a ( g ，d ) = m i n m l g h a sd l d ( 2 ，1 ) 一l a b e l i n g w i t h ，i ol a b e l 9 r e u t o t h a n m ) 定义f i f ( a ) | = m a x f ( v ) ： v ( g ) ) ，刚a ( g ，d ) = m i n i _ f ( a ) 硕士学位论文 这里g 中的点代表电台，如果两个电台十分接近，必须使用相差足够远的频道，则在图g 中代表这 两个电台的点“，u 满足，v ) e ( g ) ：如果两个电台比较接近，需要使用有一定区别的频道时，点乱，口满 足d ( u ，口) = 2 在所有的点上指定值，( 代表电台使用的频道) 条件，( 1 ) ，( 2 ) 就保证了各电台之闻不捃 互干抗我们的目标就是在所有满足条件( 1 ) ，( 2 ) 的频道分配中，寻找使用频道资源的最少的分配，也 就是这里的最优分配。 上面的数学模型清楚的描迹了频道分配问题的约束和目标，但是这里提出的着色使用了实数的 概念，和通常意义下圈的着色( 用整数值来给图中的点着色) 有一定的区别池给研究该问题带来了麻 烦。如何将这个新的着色问题和通常意义下的着色联系起来呢? g r i g g s 和y e h 在f 1 5 1 中很好的解决这 个问题 1 2 图的三( 2 ，1 ) 一l a b e l i n g 着色 由上一节中给出的标号着色定义，我们发现这个定义和通常的着色定义有两点区别： ( a ) 点着的颜色不是整数值： ( b ) 在约束中，点的颜色之问差值不是整数值。 g r i g 驴和y e h 在f l5 】中给出了下面两个引理： 引理1 2 1 - z ，可0 ，d 0 ，k z + ，如果i 。一可f k d ，那幺j 一一掣，j k d ，其中z 7 = x d j d ，”7 = l d j d 。 g 理12 2 对赶摩的实数d ，a ( g ，d ) = d a ( g ，1 ) 。 这两个引理事实上解决了上面所说的两个问题n r o b e r t s 提出的图的标号着色和通常的点着 色建立的联系：对于任意的实效d o ，如果函数，满足约束( 1 ) ，( 2 ) ，取，( u ) = l ，( ”) 列d v v y ( g ) ，那么，7 也满足约束( 1 ) ，( 2 ) ；如果a ( g ，d ) = i l f l l ，其中，是g 的一个( 2 ，1 ) 一l a b e l i n g i 萤数，那么 存在g 的一个整数值的工】( 2 ，1 ) 一f 口6 e “n 口函数，i 满足，：d + f 所以有下面的定理： 定理1 2 - 3 对于任摩的田g ，存在一个整数值的l 1 ( 2 ，1 ) 一l a b e l i n g 函数f ：y ( g ) _ ( o ，1 ，2 ，) ，使 得j j ，( g ) | 】= a ( g ，1 ) 。 这样有关于圉厶( 2 1 ) 一2 n 6 e “n 9 问题的研究就只需要考虑整数值的上，( 2 ，1 ) 一l a b e l i n 目问题了。 有关于这方面问题的讨论主要有这些文章： 2 】， 6 ，【1 2 】，【1 3 ， 1 5 】，【1 9 】。以后，我们将己。( 2 ，1 ) 简写 ) 4 j l ( 2 ，1 ) 1 3 图的列表着色数( 1 i s tc h r o m a t i cn u m b e r ) 图的标号着色的概念能够很好的描述频道分配的模型，现在我们要对原有的模型加瞄修改。 事实上在现实世界中，并不是所有的频道资源都可以提供给电台使用的，有些电台因为种种的原 2 硕士学位论文 因不能够使用某些频道。也就是说，对于上面所说的函数，它的值域不再是 o ，l ，2 ，) ，而是l 。 f 0 ，l ，2 ，) ，这里的l 扣) 是点。可以用来着色的颜色集合。这个概念并不是一个新的概念，它来自于图 的列表着色数( 1 i s t c o l o r i n g ) 的概念。 定义1 3 1 目g ( u e ) ，对每个占。，l 。z 是吉可用的颜色集合，称为口的颤色列表函数c 是囤g 的 一个列袁者色门j s cc o l o r i n g ) 如果c 满足 口jc ( 口) l 。，y ( g ) i c ( v ) c ( u ) ，( ， ) e ( g ) 。 如果对于在意的颜色列表，只要! 三( ”) j2kv u y ( g ) ，就存在一个g 的列茬着色，我们崴称 田g 是k - c h o o s a b l e 。 图g 的列隶着色教( g ) ：( g ) = m i n kj c i s k c h o o s a b l e 。 有关于l i s t c o o r i n g 的一些结论可以在( 1 】( 1 8 】，【2 l ，【2 3 1 ( 2 4 】，【2 5 1 ，【2 6 】，f 2 7 】申拽刘 当我们把列表的概念加入到原来的标号着色的定义中时，就可以比较好的描述新的频道分配横 型： 定义1 3 2 对于筒单r a g ( v , e ) ，目的列表标号者色是一个整教值函数f ： v ( a ) 一l 。v y ( g ) ，供中l 。z 是，点u 的可用颜色列袁，) 满足条件： ( 1 ) i ，( t t ) 一，( u ) j 2 ( 玑，j 1 e ( c ) ( 2 ) j ，( b ) 一( 圳1d ( u ，。) = 2 如果对任意的满足i l 。i k v v v ( c ) 的颜色列隶，图g 都可以找到一个浦足条件的着色，就 稚g 馒k - l ( 2 ，j j c h o o s a b l e 固g 的列表标号着色数定义为： ( g ) = m i n k l g2 s 一l ( 2 ，1 ) 一c h o o s a b l e 在下一章中，我们将给出列表标号着色敷的更一般性的定义。 1 4 图论的基本符号和概念 本文中，我们用g = ( k f ) 表示一个图，其中v 是圃的顶点集合，e 是边的集合除非特别说 明，否则这里的围都将是简单的无向图，也就是说，两个点之问至多只有一条边，所有的边都是无向 边如果e = ( ，u ) e ( g ) ，就称点u ， 相邻，边e 与点“，u 关联点”的度是所有与它关联的边的个 数，记为d ( ) 或d g ( ) 。点u 的邻域p ) 是指所有与其相邻的点妁集台。集合x y ( g ) 称为图g 的独 立集，如果任意的两个点“，u x 均不相邻。图g 的最大度( g ) 是图中所有的点中度的最大值：z x ( a ) = m a x a ( v ) v v v ( g ) ；图g 的最小度6 ( g ) 是图中所9 - 的点中度的最小值：6 ( g ) = m i n ( d ( v ) v v v ( a ) 。图g 的顶点数记做n ，边数记做m 。 图= ( v 7 ，e ) 是圈g = ( k e ) 的一个子圈，如果y 至y ，e e 且_ u v e ，叫口v ， 如果同时有e = ( u v b ，u v ，州：l e ) ，那么就 | 6 ：图h 是图g 由点集v7 的导出子图逼常记 为e l y 饥 硕士学位论文 图g = f 矿e ) 中的一条路r = v l 2 u 。，( 这里 ，t = 1 ，2 ，n 是图中的点，) 如果( 卜1 ，口。) f ( g ) i = 2 ，n 。如果同时有( 口l ， 。) e ( g ) ，那么就称这是圈g 的一个圈，记为c - 。路和圈的长 是指它们所包含的边的个数：只的长度为佗一1 ，g ：的长度为n 。 如果图g 中的两个点“， 之问存在一条路，鄢么就称u 和u 是连通的，两个点之间的距离是指它们 之问最短路的长度，记为d ，u ) 。如果u ，口是不连通的，那么d 扣， ) = 0 0 。如果图g 中任意两个点之间 都连通的那么就说图g 是连通图。若图g 是连通图，而图g 一 不连通，就称点是图g 的割点。对于 g f l g ，如果至少要去掉k 个点，才能使其不连通，就称g 是k _ 连通图雷g 的连通分支是指其极大的连通 子图。它的连通子图的个数称为连通分支数。图g 的一个块是没有割点的极大连通子图 接下来我们介绍几个基本的图类： f i ) ：图? 称为辛对，如果它是连通的且不合有圈的图。 ( j i l 一图k 。称为完全图，如果l v ( k 。) i = 礼且k 。中的任意两个点均相邻。 ( i i i ) ：图g ( x ，y ) 称为二部图，( 这里n x ，y 是两个独立集，) 如果v 扣，u ) z ( a ) ；u x ， y 或 rv x 。 ( i v ) ：平面图：所有的图都可以在平面上画出来如果我们可以把图g 在平面上画出来，使得所有的 边除了在，点上以外都不交叉，就祢这种画法是圈g 的一个平面嵌入。如果图g 存在这样的平面嵌 入，就把g 称为平面图。平面图g 把整个平面分成若干个连通的区域，我们把这些连通的区域称为平 面图g 的面厂。平面目g 所有面的集合记为f 。在f 中有唯一个没有边界的面，称为雷g 的外面。如果 点u 或边e 在面，的边界上，就称。o , v ，边e 与面，关联。如果两个面，。，2 与同一条边关联，就称 ，2 相 邻。面，的度d ( r ) 是指与其关联的边的个数，这里若一条边的两边区域是同一个面，那么计算这个面 的度时这条边要计算两次。每个平面图都有其偶图g ：( 1 ) g + 中的点与g 中的面一一对应；( 2 ) g 中的 两个面相邻铮它们在g + 所对应的点相邻。( 3 ) g 中一条迫的两边区域是同一个面铮在g + 中所对应的 点上由一条到自身的边。 此外我们用f o ，七1 采示集台0 ，1 ，2 ，南。 东南大学硕士学位论文 第二章 定义及基本的结论 2 1定义 有了上一章中的介绍藏们先给出关于标号着色和列表标号着色的一般性的定义。 定义2 1 。1 图的标号者色教：d l ，d 2 是两个菲负整数四g 的一个l ( d l ，d 2 ) 一l a b e l i n g ： ，是一个 母g 的而，点集台y 到整数集合【o ，州的一个珙射。映射l 似l ，d 2 ) 一l a b e l i n g ，称为正常着色，要涝足 条佯： l ，( 札) 一，( u ) l d 。l s i 2d ( 钍，u ) = i ( u ，甜y ( g ) ) 图的标号着色教a 8 z 山( g ) 定义为： m i n aj a r a p h ga d m i t sa l ( d l ，d 2 ) 一l a b e l i n gs a t i s f y i n g t h e c o n s t r a i n t s 在技有歧义的情况下，茼毕的记为：a 血，如。 从上面的定义推广我们可以给出图的列表标号着色效的定义， 定义2 1 2 目的列袭标号着色嫩：d 1 ，d 2 是两个非负整敷。母g 的一千正f ( d l ，如) 一l a b e l i n g ：，是 一个目g 的罚，点集y 到整戥集合 l 。j ”y ( g ) ) 的一个_ 辨射，使得，0 ) l 。，其中l 。是顶点 的可 者色颜色集耿射厶( d 。，d z ) 一l a b e l i n g ，称为正秽者色，要满足条件： f ，( “) 一，( ) 三破，ls i 2d ( u ，u ) = i ( 缸，u y ( g ) ) 如果对在薄满足i 上。j v 口v ( a ) ，都可以找到g 的一卜正常者色，就静g 是一l t ( d - ，d 2 ) c h o o s a b l e 目的列袁标号着色教a ? 1 i 南( g ) 定义为j a ? 1 l 也( g ) = m i n kf g r a p h gi s k 一二l ( d l ，d 2 ) 一c h o o s a b l e ) 在不产生教义对，筒单圮为：川7 以后，我仍用l ( y ) 表示对于目g = ( k e ) 一母绔定的颤色列 未。 有了上面给出的关于a 山d ，( g ) 和硝- ，如( g ) 定义，可以得到， 5 一 东南大学硕士学位论文 定理2 1 1 对于任意的四： a ? 埘2 ( g ) 2a d l , d 2 ( g ) + 1 ；vd l , d 2 i n t e g e r s 螽疆2 1 2 对任意曲翟g ，有下面的结论 ( 1 ) “1 a 一1 司 f 2 ) 2 1 1 删 ( 3 ) a 。1 + i 【1 5 j 同样的关于凡有结论 命题2 1 3 对任意的田g ，有 ( 1 ) 廿1 ( 2 ) a j 1 + 1 ( 3 ) 廿1 + 2 我们可以验证蜀标号及列表标号着色鼓都达到上面给出的下限，而凰是任何一个最大度 是的图的子图 在本文中我们将主要讨论的是图的 ；1 着色数问题，下面我们用凡表示碍”以后，我们用l ( y ) 表 示对于图g = ( u e ) - - 个给定的颜色列表除非特别说明，任意l 。中的整敷均是从小到大排列的， 且记c = m a x a l 。v v y ( g ) ) ；c = m i n a l 。v v y ( g ) ) 2 2 路的列表标号着色数 我们用只= v l ”z 。表示包含有n 个点的路。首先我们给出一个关于路的标号着色数的结论 命题2 2 1 ( r ) 一2 ，a ( p 3 ) = 3 ，a ( p 4 ) = 3 ，a ( r ) = 4vn 5 司 我们用l ，表示v 。的颜色列表，可以证明对于列表标号着色数有下面的结论： 定理2 , 2 2 凡( 尼) = 3 ，a f ( 岛) = 4 ， 凡( 只，) = 4 ，九( r ) = 5v 竹三5 证明：由命题2 ，ll ，我们有凡( 马) 三3 ，凡( p 3 ) 24 ，a f ( r ) 4 ，凡( p n ) 5 v ，凡25 现在只 要证明对于任意达到上面下限的j l 。j ，均可以找到一个正常着色， ( 1 ) p 2 ：设l l = a l ，a 2 ，n 3 ) ，l 2 = ( b l ，b 2 ，b 3 ) ，如果a 1 = c ，则6 3 n 1 + 1 ，我们可以 让，( ”，) ：a l ，( ”。) = 如。这是一个正常的着色。如果b 。= e t 可以做相似的讨论。 ( 2 ) 岛：设l 1 = ( a l ，a 2 ，a 3 ，a 4 ) ，l 2 = ( 6 1 ，b 2 ，b 3 ，b 4 ，l 3 = ( c l ，e 2 ，c 3 ，岛) 。分两种情况来讨 论：c a s e 1 ：b 1 = e ， 此时我们让，( 口2 ) = = = 6 z ，则对于”t ，啦来说均至少有两种颜色的选择，这样可以保证r ，) - ，( ) 。 c a s e2 ：a l f ( 1 7 t db i2e + 1 硕士学位论文 c a s c2 ：a l = cn 7 谢b l c 十1 让，( 1 ) = n 。，此时对于口。，忱来说均至少还有三种颜色可毗选择，由上面的讨论 ( r ) = 3 ，这是可以正常者色的。 ( 3 ) 乃设l - = a 。 ，l 2 = ( b 1 ) l 3 = c i ) ，l t = d ，) ；z = l ，2 ，3 ，4 ，分情况讨论： c s el ：b 1 = c 让，( w 。) = b ，这时嘶，均均至少有两种剩余的颜色 。3 ，a 4 ) 和 c 3 ，c 4 ) ，m 至少有三种剩余的颜 色 如，d 3 ，血) 首先给口3 着色，假设当，0 3 ) = c 3 时，舢无法正常着色，印如= c 3 1 ，d 3 = c 3 ，d 4 = e 3 + l ，则让f ( v a ) = c a ，可以保证幽正常着色，而 ，可以在 a 。：a 4 ) 中选取，保证，( - ) f ( v 3 ) 如果c l 2 ，l 3 ；e 幻，同样可以证明可以正常着色。 c a s e2 ：c ，c r iu 三4 且c ，g g 三2 u 三3 如果e _ l - 且c l n ，那么让，扣- ) = f ( v 4 ) = c ，则u 2 ，均均至少还有三种颜色可用，这是可以正 常着色的同样如果c l ，且g l 。，我们也可以正常着色p 4 。所以，不失一般性假设c l ：，c l 且g 岳l l ，c g 上4 ，此时让，( 1 ) = c ，f ( v t ) = c ，则啦，啦均至少还有三种颜色可用，可以正常着色。 ( 4 ) 只：设l ：= 弓，j = l ，2 ，5 ，我们给出一个着色方法，首先，( 口，) = c i ，此 时， z 的颜色列表中至少有两种颜色可毗使用，给v 2 着色，接下来让，( 口。) 选取l 。中可能的最小 值2 = 3 ，4 ，n 。因为，u ，由扯一z 造成三种颜色不可以使用，由让2 造成有一种颜色不可以使用，即 其列表中至多有四种颜色不可以使用，而f l 。i = 5 ，所以可以保证其正常着色 事实上，我们可以发现印使我们不从v - 开始，而对任意点地着l 。中的任意颜色，都可以给 出r n 5 一个正常着色，也就是说当l l 。i25 ，v y ( g ) 和n 5 时，对于任意指定的 点”和l 。中的任意颜色c ，均存在一个正常的丑一 a b e z i n g ，使得f ( v ) = c 。 2 3 完全图k 。和树的列表标号着色数 定理2 3 ，1 对于任意的芜坌图蜀，凡( 蟛。) = 2 n l 证明：按顶点的个数扎进行归纳法。因为耳2 = 尸2 ，所以由上面的讨论我们有 ( 耳：) = 3 。 假设( 玩一- ) = 2 m 一1 ) 一1 ，我们考虑j ( 。，对于任意满足1 l 。1 2 n 一1v v 的l ， 设c 上n ，则让，( 。) = c ，此时k 。口= 甄一1 ，而对于吐i ( 1 ，n l 】，i l ( v 。) f 2 n 一1 2 = 2 ( n 一1 ) 一l ，其中l ( u ：) 表示在l ：中去掉因着色而不可以使用的颜色后的颜色列表。由归纳假 设，k i 在新的颜色列表( u ) v v k n l 中有正常着色，。定义，( u ；) = a q ) v i f l ，n 1 。则 我们得到的一个正常的凡一l a b e l i n g 。 定理2 3 2 对于树丁，有凡( = a + 2 或+ 3 。 证明：首先我们将证明对于星。，有a ! ( l ，) = + 2 。 事实上，a f ( 1 - ) = ( ：) = 3 。假设( t ，。一1 ) = n + 1 ，对于( 1 。) ，度为n 的记为， 其它度为1 的点记为让，2 = l ，2 ，竹。任意给顶点曲颜色列表厶= f c ；，歹= l ，2 ，3 ， ，i i 。j 十2v i ，分情况讨论 硕士学位论文 c a s el ：卅= c 让，( t ，o ) = c ? ，则此时对于其它的点颜色列表中至多有两种颜色不可使用，即新的列2 女l ( v 。) 满 足 l ( v 。) i a + 2 2 = i = 1 ，2 ，n ，可以保证所有的点都可以得到不同的着色。 c a s e 2 ：c i = c5 o 且c o c 让，( ) = c i ，此时新的颜色列表三( 饥) i = 0 ：1 ，扎a n di s ，满足l l ( v ，) i a + 1 。 而- ，。一。= k l ，。一，由归纳假设，存在一个正常的着色，我们可以将这个着色推广到k l 。上得 到一个正常的着色。 对于树，由于任意一个最大度为的树均有。子图，所毗h ( t ) a + 2 下面我们证 明：( 丁) + 3 这里我们给出一个树的着色方法，首先将所有的点排序为u o ，叽：，u 。使得址与 咖，u ， v i 一，) 中唯一的一个点相邻，从u o 开始，每个 。映射为l t 中可能的最小值i = 0 ，1 ，n 因为饥只 与( ，吡，q 一， 中的唯一一个点相邻，以及至多a 1 个点的距离为2 ，所以在其颜色列表中至多 有3 + 一l = + 2 个颜色不可以使用，对于任意三。0 = 0 ，1 ，n ) 只要j l 。f + 3 ，就保证树可 以正常着色。 2 4 对路的列表标号着色的进一步讨论 论 从前面的讨论我们已经得到了路的列表标号着色数，下面我们对路的列表标号进行避一步的讨 2 4 1正常列表的定义 定义2 4 1 团g = ( k e ) ；v = 口l ，u 2 ，v ) ，如果对于任意满足i l 。i = a 。i = 1 ，2 ，n 的颜色 列袭，围g 都可蹦正常者色，我们就称图g 在廓色列袅( 。，a z ，a 。) 下是可以正常着色的或颜色列 袁- ，a 2 ，。) 可正咎者色图g 。筒称为缸，a z ，n 。) 是g 的r 正常列袭。 在此定义下我们不难得到下面的结论： 命题2 , 4 t p 2 莅( 2 3 ) 和( 1 ，4 ) 下是可以 正常者色的 命题2 4 ，2 - 如果( d ，n 。，a 。) 可正学者色r ，刚p n 在( d a 一- ，n 1 ) 下也可以正常者色。 命题2 4 3 如果( o i ，n ，a 。) 可正学者色r ，那幺者( b l ，b b n ) 满足6 ：a 。i = l ，2 ，n ， 则( b - 、b z ，b ) 也可以正常者色r 。 如果p n 在( b 1 b 2 ，d ，) 下不可以正常考色，则对任意( n 1 ，a ”n 。) 满足b 。啦，i = l ：2 ，唆也 不能正常着色 命题2 4 4 如果( j 、毗a ) 可正常者色p n ，剧( l ，n 2 ，a5 ) 可正带着色只+ 8 一一 塑主茎堡丝查 引理2 4 5 r 在( d ，一z ，n “) 下可以正秽着色的窟要条件点只+ r 在。，。舻i + i ，。+ 3 ，1 ) 下 可正常者色 证明：i i p n + i = ( 吼，。+ 1 ) 。i ：i = 啦1 = l ，2 p ，n 一2 ， i l 。一l = 8 。一z + l ， 厶。 = n n + 3 ，三n + l = n ) 。j i f ( v - ) ；。，使得 。一- 至多有一个， 。至多有三个颜色不可以使用。因 为只- 在( a l ， ，a n - - ，t ) 下可以正常着色，所以此时p 兀+ 。是可阻正常着色的。 假设r 在三z 下不可以正常着色，其中j ：f ；o ；，i = l ，2 卜，n 。夸e = m a x f 。l ，、i = i ，2 ，n ) ，对p n + l 我们取这样一个颜色列表：厶= 工，z = l ，2 ，n 一1 ；。一i = l 。一1u f c + 2 ；l n = l n = u c + 1 ，c + 2 ，g + 3 ；三。+ l = c + 2 ) 。由假设，不难发现r + i 在此列表下是 不可以正常着色的，即只冲，在国，8 。一i + 1 ，8 。十3 ，i ) 下不可以正常着色。 引理2 , 4 6 u ，叫是目g 中相筇的两个童，i l 。l = 盎，l l 。l = 惫+ 1 ，则l 。中至少有仓颜色可以擐 证厶：，中曲不少于一1 种筋崔可厢。 证明：因为i l ”, i = + l ，则满足( 一l ，n + 1 jc l 。的颜色n 至多有晃一1 个，而i l 。i = 盘可以保 证至少有一个颜色满足t “仍有七一1 种颜色可用 引理2 - 4 7 妇栗只一在( 吼，8 2 ，口。一- ) t c ，只。茬( 6 。，屯，6 m ) 下砖可以正碧者色，删在( n3 ，8 2 ，8 n i + l ；b i ，b ，6 m ) 和( o l ，2 ，a n - l ；b l + 1 ，6 2 ，h ) 下，r + m 一可以正常着色，其中 给r + 。一 。者色表哥 磬只+ 。中腧。外所有的席者色。 证明：对r + m = - u n 上m ，设i 厶j = a i , i = 1 ，2 ，1 n 一2 ；i l 。一j i = a n - i + i ；i l 。+ ，j = b - ，= 1 ，2 ，m 因为r 在( b lb 。， ，6 m ) 下是可以正常着色，我们先给u 。+ ： 着色，这 将造成l 一，中至多有一个颜色不可以使用。而只：一- 在( n ，。一，) 下是可以正常着色，所以 当u n 不着色时，上面曲结论成立。 对( 。l ，( 2 2 ，n 。一【；6 l + 1 ，6 2 ，b m ) 也有同样的结论， 引理2 4 8 一只+ m + 1 在( ，。n ，l ，b 6 m ) 下可以正带毒色的茏要条伴是r + m + 。一础。+ l 在( 。l 。一1 1 ，一3 ；b i 一3 ，6 2 1 ，b 。) 下可以正常者色。 证明：这个引理可以由引理2 45 和247 直接得到。 2 4 2 尼，只的正常列表 定理2 4 9 p 3 在( 2 ，4 ，3 ) ，( 1 ，4 ，5 ) ，( 4 ，1 ，5 ) ，( 1 ，5 ，4 ) ，( 2 ，3 ，5 ) ，( 3 ，2 ，5 ) ，( 3 ，3 ，4 ) ，( 1 ，7 ，2 ) ，和( 1 ，6 ，3 ) 下 是可以正喾者色的。 证明：设b = x y z ： 坚生盟： 令- l z = ( o l ，n 2 ) ，l v = 6 。，i = 1 ，2 ，3 ，4 ，l ：= c i ，c 2 ，c 3 ) 硕士哮位论天 因为z ( 一，b 。一2 】u b 。+ 2 ，。) ，所以上l 中至少有三种颜色( 相同颤色要重复计数) 在( 一c , o ，b 。一2 或【6 。r _ 2 ，) 中。t - 失一般性，假设至少有三种颜色在【6 1 十2 ，。) 中，g 是 f f l 分情 况讨论： c a s el ：如果l 。n i b 】4 - 2 ，c o ) = 0 ，那么l 。i b l + 2 ，o o ) ，且口l 墨b 1 。此时让，( 。) = 0 1 ，y ，。分 别至少还有2 ，3 中颜色可用而p c x ( 2 ，3 ) 是可正常着色的。 c c2 ：如果l 。n h + 2 ，。) 0 ，则让，( ) = bj ，而：f ，2 均仍有颜色可用，且其中- + a 可用颜 色数大于2 ，印z j ：在( 1 ：2 ) 是可以正常着色的。 ( 1 4 ，5 ) ，( 4 ，1 ，5 ) ，( 2 ，3 ，5 ) ( 3 ，2 ，5 ) ： 我们可以从上面的命题24l ，命题24 2 和命题2 4 4 得到p 3 在这些颜色列表下可正常着色。 亟业： 可从命题2 4 1 ，命题242 和引理245 得到结论。 ( 3 ，3 ，4 ) ： 如果jk l 。使得l 。 惫一l ，盘，k + 1 ) 且l l ：n ( 恕一1 ，是，k + 1 ) l 2 ，则让，( 掣) = 恕， 而z ；z 在( 1 ；2 ) 下是可以正常着色的 如果满足条件的七不存在，则v 七l 。，有l 。= ( 七一1 ，k ，惫+ 1 ) 或( k 一1 ，k ，七+ 1 ) cl ：。因为l l 。f = 3 、i l ：i = 4 ，所以至多有一个整数是前式成立，两个连续的整数使后一个成立也就是说，如果满 足条件的七不存在，则有：l ：= “一1 ，+ 1 ) ，l 口= f f ，h + 1 ，矗+ 2 ) ，l ：= h ， + 1 ，h + 2 ，危+ 3 ) ，其 中，h ，f z 。如果f h ，则y ( x ) = f 一1 ，( g ) = h 十2 ，f ( z ) = 是一个正常着色；如果f 2h + 3 ， 则，如) = f 十l ，国) = + l ，f ( z ) = h 十3 是一个正常着色( 事实上因为i 工。l = 3 所以l h + 3 或z 兰h ) 竖! ! 塾i ! ! ! ! 兰2 = 可从命题24l 和引理245 得到。 定理2 4 1 0 只在( 3 ，4 ，4 ，4 ) ，( 2 ，5 ，4 ，3 ) ，( 2 4 ，5 ，3 ) 下可以丘移着色 证明：设p 4 = w x ! z ，记g = m a x a l pv ) ；c = m i n a l 。讹) 。 ( 3 ，4 ，4 ，4 ) ：分以下的情况讨论 c a s e 1 c ，田仁l 。t j l 不失一般性，设c 隹l ：ul v ，则c l 。ul ：。如果c l 。，让，) = c ，得到z 可z 列表满 足( 3 ，4 ，4 ) ；如栗c l ：，让，( 2 ) = c ，得到w z y 梦 j 表满足( 3 ，4 ，3 ) 。由定理249 ，这些都是正常列 表。 c a s e2 ：k e ) c l 。ul ( a ) c ，g ) 仁l 。不失一般性，设cgl 。，如果c l 。，让，( 可) = c ，n w z ；z 颜色列表 满足( 3 ，2 ；2 ) ；如果c l 。且c l p ，让，( z ) = c ，则训；掣z 颤色列表满足( 2 ：3 ，3 ) 。由命题24 l 和引 理2 47 ，我们可以得到这都是正常列袁。 ( b ) c ，g ) l 。： 硕士学位论文 ( 1