（运筹学与控制论专业论文）关于图的均匀染色.pdf

摘夏 关于图的均匀染色 摘要 图的染色理论是图论研究的热点问题之一图的均匀染色理论 作为图的染色理论的一种特殊情况，在较早的时候就已经被提出，它 在工业生产、企业管理和生物学等领域中都有广泛应用，特别地，在 研究时间表、剖分、承载平衡等问题中，均匀染色理论起着举足轻重 的作用但发展至今，关于此理论被解决的问题很少近年来，随着图 的列表染色研究得到广泛关注，人们继而开始研究均匀列表染色，但 有关这方面的研究结果较少本学位论文主要研究图的各类均匀染色 问题，全文由四章组成 在第一章，我们主要是对本学位论文涉及到的问题的背景、定义 及进展等各方面进行一个综述 在第二章，我们主要研究了平面图的均匀列表染色2 0 0 3 年， k o s t o c h k a ，p e l s m a j e r 和w e s t 提出了两个猜想：若七a ( c ) + l ，则图 g 是七一均匀可选择的；最大度不小于3 且不为完全图和憨。+ 1 2 。+ 1 ( m 1 ) 的连通图g 是( g ) 一均匀可选择的我们利用权转移的方 法分析了不含某些短圈的平面图所必须含有的一系列特殊结构从而 证明了最大度至少为8 且不含3 一圈的平面图，最大度至少为7 且不含 4 一圈和5 一圈的平面图，最大度至少为8 且不含4 圈和7 圈的平面图满 足这2 个猜想此外我们也证明了外平面图满足这2 个猜想 在第三章，我们主要研究了平面图的顶点均匀染色1 9 7 3 年， m e y e r 提出了一个猜想：若连通图g 不为完全图和奇圈，则x 。( g ) ( g ) 1 9 9 4 年，b 一l c h e n ，k - w l i h 和p - l w u 进一步提出了：不为 k r n ，岛。+ 1 和鲍。+ 1 ，2 m + 1 ( m 1 ) 的连通图g 是( g ) 一均匀可染的 围绕这2 个著名的猜想，我们把第二章的结论平行推到平面图的均匀 染色中来，从而得到最大度至少为8 且不含3 圈的平面图，最大度至 少为7 且不合4 一圈和5 一圈的平面图，最大度至少为8 且不含4 圈和 摘要 7 圈的平面图满足这2 个猜想 在第四章，我们主要研究了联图r v 。的均匀全色数2 0 0 2 年， 王维凡猜想：无环图g 满足x , t ( g ) z x ( c ) + 2 ，其中x 。t ( g ) 表示g 的均匀全色数我们证明了联图r v n 满足该猜想，且当m t , - - 2 时，有。t ( rv ，。) = ( rv ，。) + 1 关键词：顶点均匀染色，均匀列表染色，均匀全染色，平面图，圈 一【l 一 a b s t r a c t e q u l l i a b l ec o l o r i n g so fg r a p h s a b s t r a c t t h i sd i s s e r t a t i o ni sd e v o t e dt os t u d yt h ee q u i t a b l ec o l o r i n gp r o b l e m s a n di tc o n s i s t so ff o u rc h a p t e r s i nc h a p t e r1 ，w ei n t r o d u c es o m ed e f i n i t i o n sa n dn o t a t i o n su s e dt h r o u g h o u tt h i sd i s s e r t a t i o na n dg i v eac h i e fs u r v e yo ne q u i t a b l ec o l o r i n gp r o b l e m s u n d e rc o n s i d e r a t i o n i nc h a p t e r2 ，w ed i s c u s st h ee q u i t a b l yl i s tc o l o r i n g so fp l a n a rg r a p h s i n2 0 0 3 ，k o s t o c h k a ，p e l s m a j e ra n dw e s ti n t r o d u c e d2c o n j e c t u r e s ，o n e s t a t e st h a te v e r yg r a p hgi se q u i t a b l yk - c h o o s a b l ew h e n e v e rk2a ( c ) + 1 a n da n o t h e rs t a t e st h a ti fgi sac o n n e c t e dg r a p hw i t hm a x i m u md e g r e e a 3 ，t h e ngi se q u i t a b l ya c h o o s a b l eu n l e s sg i sac o m p l e t eg r a p ho r i sk 2 m + 1 2 m + 1 w ep r o v et h a tgs a t i s f i e st h e s et w oc o n j e c t u r e si fgi sa t r i a n g l e - f r e ep l a n a rg r a p h sw i t hm a x i m u md e g r e ea tl e a s t8o rg i sap l a n a r g r a p h sw i t hm a x i m u md e g r e ea tl e a s t7a n d w i t h o u t4 - c y c l e sa n d5 - c y c l e s ， o rgi sap l a n a rg r a p h sw i t l rm a x i m u md e g r e ea tl e a s t8a n dw i t h o u t4 - c y c l e sa n d7 - c y c l e s f u r t h e m o r e 。w es h o wt h a tt h e s et w oc o n j e c t u r e sh o l d f o ro u t e r p l a n eg r a p h s ， i nc h a p t e r3 ，w ei n v e s t i g a t et h ee q u i t a b l yc o l o r i n g so fp l a n a rg r a p h s i n1 9 7 3 ，m e y e ri n t r o d u c e dt h en o t i o no fe q u i t a b l ec o l o r i n ga n dc o n j e c t u r e dt h a tt h ee q u i t a b l ec h r o m a t i cn u m b e ro fac o n n e c t e dg r a p hg ，w h i c h i sn e i t h e rac o m p l e t eg r a p hn o ro d dc y c l e ，i sa tm o s t ( g ) i n1 9 9 4 ，b - l c h e n ，k - w l i ha n dr l w up u tf o r t ht h ec o n j e c t u r et h a tac o n n e c t e d g r a p hg i se q u i t a b l y ( g ) 一c o l o r a b l ei f i ti sd i f f e r e n tf r o mk n ，q m + 1a n d k r 2 m + l 2 m + 1f o rm 1 w ea p p l yt h er e s u l t si nc h a p t e r2t ot h ee q u i t a b l e c o l o r i n g so fp l a n a rg r a p h sa n dp r o v et h a tg s a t i s f i e st h e s et w oc o n j e c t u r e s i fgi sat r i a n g l e - f r e ep l a n a rg r a p h sw i t hm a x i m u md e g r e ea tl e a s t8o rg 1 1 1 - a b s t r a c t i sap l a n a rg r a p h sw i t hm a x i m u md e g r e ea tl e a s t7a n dw i t h o u t4 一c y c l e s a n d5 - c y c l e s ，o rgi sap l a n a rg r a p h sw i t hm a x i m u md e g r e ea tl e a s t8a n d w i t h o u t4 一c y c l e sa n d7 - c y c l e s c h a p t e r4i sd e v o t e dt oc a l c u l a t et h ee q u i t a b l et o t a lc h r o m a t i cn u m b e r o f j o i ng r a p hp nvk m ”i n2 0 0 2 ，w a n gw e i f a nc o n j e c t u r e dt h a t ) ( e t ( g ) a ( c ) + 2h o l d sf o ra n yg r a p hg w ep r o v et h i sc o n j e c t u r eh o l d sf o rj o i n g r a p hp nv ，mf u r t h e r m o r e ，w ep r o v et h a tx e “rv ，n ) = x ( rv m ) + 1w h e nm 竹一2 k e yw o r d s ：e q u i t a b l ec o l o r i n g ，e q u i t a b l el i s tc o l o r i n g ，e q u i t a b l et o t a l c o l o r i n g ，p l a n eg r a p h ，c y c l e i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 研究生签名：拗 学位论文使用授权声明 日期：谚加抄 | 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生签名毛斋商铳着翩豁) 。) 稗隰渺1 7 抄v l 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：拗 指导教肌，擗 一、绪葩 ( 一) 、 基本概念 一、绪论 在本章中，我们先给出一些本学位论文中要用到的图论的基本术语与符号 对本章中没有给出的术语与符号，我们会在后面合适的地方给出对于那些文中 没有给出的术语与符号，可以在【l 】中找到本文所用术语和符号基本上与文献 【1 】一致 一个无向图是一个有序对g = ( v e ) ，其中y 是一个有限集合，e 是y 中的 不同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图g 的 边我们通常用v ( c ) 和e ( c ) 分别表示图g 的顶点集合和边集合没有重边和 环的图叫做简单图除非特别指出，本文研究的图均指有限简单无向图对于图 g 中的顶点和 ，若边e = t t v e ( g ) ，则称 t t 和1 ，相邻，乱和t ，互为邻点；称“ 和口是e 的端点，札和v 分别与e 关联若g 的边e 和，有一个公共端点，则称e 和r 相邻在图g 中与顶点u 相邻的顶点的全体叫作t 的邻域，记作0 ( 札) 称 i | g ( u ) i 为顶点 i t 的度数，记作d g ( “) 称度数为k 的顶点为七点g 中顶点的度 中最大者和最小者分别称为g 的最大度和最小度，分别记作a ( c ) 和d ( g ) 在 不产生混淆的情况下，我们把y ( g ) ，e ( g ) ，g ( u ) ，d g ( u ) ，( g ) ，d ( g ) 分别简记为 v e ，( u ) ，d ( u ) ，6 对于图g = ( v e ) 和图h = ( v ，e ，) 若有y y ，e 7 e ，则称图h 是图 g 的一个子图对于y 7 y ( g ) ，我们把图g 中属于矿7 的顶点以及与y 中的点 关联的边都删除所得到的图记作g y 7 或g y 7 对于y 7 y ( g ) ，我们把由矿7 作为顶点集，e 7 = e i e = 伽e ( g ) ， v ) 作为边集的图叫做g 中由顶点子 集y 导出的子图，记作c v ，1 图g 的一条途径是一个有限非空的点边交替序列“j = 加e 1 1 e 2 e k v k ，使 得对1 i m a x a ( g ) ，7 ，则g 是七一均匀可选择 的，同时，g 也是一均匀可染的 ( 3 ) 若平面图g 不含4 一圈和7 一圈且k m a x a ( g ) ，8 1 ，则g 是均匀可选择 的，同时，g 也是k 一均匀可染的 ( 4 ) 外平面图满足猜想1 2 ，1 9 在第四章，我们研究了联图f ；v a r m 。的均匀全色数证明了x 。( r v 、。) s ( r v ，。) + 2 ，且当m 一2 时，地( r v ，。) = ( r v 。) + 1 本学位论文运用的思想方法主要有： ( 1 ) 运用e u l e r 公式和d i s c h a r g e 方法找到了几类不含短圈的平面图所必须含 有的一系列结构，从而根据均匀列表染色和均匀染色的延拓性得到了一些结果 ( 2 ) 通过在原图中添加一些点和边，然后运用转移颜色的方法求得了一类特 殊图的均匀全色数 ( 3 ) 巧妙地运用了图的退化性及匹配的作用， 一6 一 二、平i j i i 图“, jj j j 匀列表染色 二、平面图的均匀列表染色 在本章，我们主要考虑不含短圈的平面图的均匀列表染色 设g 是一个平面图，用d g ( z ) ( 简记为d ( z ) ) 表示一个顶点或者一个面。在 g 中的度如果d ( v ) = k ( 或d ( v ) ) ，则称顶点v 为一点( 或矿一点) 类似地 可定义一面和矿一面对于图g ，如果6 ( g ) 2 ，则( 5 ) 一面是简单面对于简 单面。我们用( d l ，4 2 ，改) 表示一个k 一面，与其关联的k 个顶点的度分别为 d 1 ，d z ，d k 用n 2 ( u ) 表示与顶点u 相邻的2 一点的个数用n k ( f ) 表示与面，关 联的一点的个数m ；( ) 表示与顶点 关联的z 一面的个数用k ( g ) 表示图g ! 中 l 一点的个数如果图g 的任意子图日中都存在一个顶点v ，使得妇( u ) d ，则称 图g 为d 退化图 在平面图的染色方面，王维凡等在文献 3 0 】中研究了( a ) = 5 且不含4 一圈 或6 圈的平面图的边列表染色在【3 1 中研究了不含5 一圈的平面图的列表染色及 边列表染色类似于不含短圈的平面图的各种染色的结果可参见文献 3 2 3 4 】类 似于不含短圈的平面图的结构性质还可参看文献 3 5 从这些文章中得到启发， 从而考虑了不含短圈的平面图的均匀列表染色问题 ( 一) 、不含3 - 圈的平面图的均匀列表染色 引理2 1 1 2 7 】令l 是图g 的一个女- 歹0 表分配，s = x l ，。2 ，x k ) 为v ( c ) 的 一个k 顶点子集，满足i b ( ) s 1 k t ( 1 ) ，若g s 是l 一均匀可染 的，则g 是l 均匀可染的 引理2 1 2 不含3 圈的平面图g 是3 退化的 i 正n 1 ：不妨假设g 为连通图由欧拉公式易得，( d ( v ) 一4 ) + ( d ( f ) 1 4 ) = 一8 易验证6 ( g ) s3 另一方面，注意到每个不含3 一圈的平面图的子图也是不含3 一圈 的平面图，所以g 的任意子图日中都存在一个顶点 ，使得妇( u ) 3 故g 为 3 一退化图 引理2 1 3阶数至少为5 且不含3 一圈的连通平面图g 含有下列结构之一 一7 一 = 、p 曲图的均匀列衷染色 肌：d 2 ( z 0 ，加( ) 4 6 + ；+ ；2 0 当讹( ，) = 0 时：因为g 不含巩和风，所以n 3 ( ，) s2 当n 2 ( ，) = 0 且n 3 ( ，) = 2 时：，是( 3 ，3 ，4 + ，4 + ) 一面因为g 不含皿5 和日1 6 ， 所以，是( 3 ，3 ，7 + ，7 + ) 一面根据( p 3 ) “，( ，) 24 6 + 1 2 = 0 当凡2 ( ，) = 0 且n 3 ( ，) = 1 时：，是( 3 ，4 + ，4 + ，4 + ) 一面因为g 不含日1 7 一 研9 ，所以g 至多有一个4 面，记作，7 ，它关联一个3 一点，一个4 一点且另外2 个项 点的度数至多为5 和6 ，根据( r 2 ) 和( p 1 ) 一( p 3 ) ，叫7 ( ，7 ) 4 6 + j 1 3 = 一 若g 含，7 ，则其它的( 3 ，4 + ，4 + ，4 + ) 一面必定是( 3 ，4 + ，4 + ，7 + ) 一面，8 ，根据( r 2 ) 和( p 1 ) 一( p 3 ) ，有叫，( ) 4 6 + 1 2 + 1 = 0 若g 不含矗，则( 3 ，4 + ，4 + ，4 + ) 一面必定是( 3 ，4 ，6 + ，6 + ) 一面，( 3 ，4 ，4 + ，7 + ) 一面或 ( 3 、5 + ，5 + ，5 + ) 一面 若，是( 3 ，4 ，6 + ，6 + ) 一面，根据( r 2 ) 和( p 2 ) 一( p 3 ) ，有t t ，7 ( ，) 24 6 + j 1 + 3 2 0 若，是( 3 ，4 ，4 + ，7 + ) 一面，根据( r 2 ) 和( p 1 ) 一( p 3 ) ，有”7 ( ，) 4 6 + j 1 2 + 1 = 0 若，是( 3 ，5 ，5 ，5 ) 一面，因为g 不含仍o ，所以( 3 ，5 ，5 ，5 ) 一面关联的5 一点中至少 有一个5 - 点不与2 - 点相邻，故根据( p 1 ) ，有训7 ( ，) 4 6 + + 2 = 0 若，是( 3 ，5 + ，5 + ，6 + ) 一面，根据( p 1 ) 一( p 3 ) ，有”( ，) 4 6 + ；2 + ； 0 当n 2 ( ，) = 0 且n 3 ( ，) = 0 时：，是( 4 + ，4 + ，4 + ，4 + ) 一面根据( r 2 ) 和( p 1 ) 一 ( p 3 ) ，有( ，) 24 6 + i 1 4 = 0 情况2 3 2d ( ，) = 5 ： 因为g 不含日1 ，所以n 2 ( ，) + 7 h ( ，) 3 故，为( 2 + ，2 + ，2 + ，4 + ，4 + ) 一面根 据( r 2 ) 和( p 1 ) ( p 3 ) ，有伽7 ( ，) 5 6 + 彳1 2 = 0 情况2 3 3d ( ，) 6 ： 此时，伽( ，) = ( ，) = d ( ，) 一6 0 因此，根据权转移规则，有一1 2 = w ( z ) = ”7 ( z ) 一2 一j 1 = 一i ， z v u tz v u t 矛盾 情况3d ( g ) = 1 ： 因为g 不含玩1 ，所以g 至多有2 个1 点，且当g 有2 个l 一点时，g 不再含 一1 3 ：、f ，i 图的均匀列衷染色 2 一点因为g 不舍3 一圈，所以k 一面( k 5 ) 为简单面 情况3 1g 中有2 个1 点： 在图g 中，1 点的总权数为( 一4 ) 2 = 一8 ，下面同情况1 来定义权转移规则 及证明( 不考虑1 一点) ，有- 1 2 = ( 。) = “j ，( z ) 一而8 9 ，矛盾 z v u f z v o f 情况3 2g 中有1 个1 点，至多1 个2 点： 在图g 中，1 点，2 一点和与2 一点关联的4 - 一面或与2 点关联的5 一面的总权数不 小于一4 + ( 一2 ) + ( - 2 ) 2 = 一1 0 下面同情况1 来定义权转移规则及证明( 不考 虑1 点，2 点和与2 一点关联的牛面或与2 一点关联的5 面) ，有一1 2 = 1 1 j ( 7 ；) = 一等，矛盾 z v u f 情况3 3g 中有1 个1 一点，至少2 个2 一点； 因为g 不含风，所以2 一点不与卜点相邻卜点的总权数为4 下面同情况 2 3 来定义权转移规则及证明( 不考虑l 一点) 若g 只有2 个2 点，则j 点伽可以 作为2 一点来考虑，但不对进行权转移，此情况同样类似与子情况2 3 故我们有 - 1 2 = ( 。) = w 7 ( g ) 一4 一；= 一萼，矛盾 o v u fo v u f 定理2 1 4 若平面图g 不含3 一圈，则对于任意k m a x ( g f ) ，8 ，g 是女一均匀 可选择的 证明：反证法设g 是一个阶数最小的反例当f y ( g ) f 时，图g 显然是一均 匀可选择的故不妨设i y ( g ) i k 8 若g 的每个连通分支的顶点数至多为 4 ，则( g ) 3 由定理1 2 2 0 ，g 是一均匀可选择的否则，g 至少有一个连通 分支的顶点数至少为5 ，又因为g 不含3 一圈，所以根据引理2 t 3 ，g 必含结构 h 1 一踢1 中之一顶点的记号与引理2 1 3 中一致如果有顶点被重复记号。则取 较大的记号( 这里我们认为勋是比z 大的记号) 根据引理2 1 3 找引理2 1 1 所要求的s 若g 含结构风或凰1 ，则记= z ，x k “z i f ；1 ) 根据引理2 1 2 ，g 是 3 一退化图，则g s 7 中有一个顶点。_ 3 ，满足d a - s ( 。k 一3 ) 3 = k 一( k 一3 ) ，再 记= o 女，z 女一l ，x k 2x k3 ，2 7 i ) 因为g 是3 退化图，所以g s ”中有一个顶 点z k 一4 ，满足d a 一酽，( 刀一4 ) 3 一( k 一4