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

山东大学博士学位论文 图的产染色和均匀边染色 张霞 山东大学数学与系统科学学院 济南2 5 0 1 0 0 指导羲师t 刘桂真 教授 中文摘要 图的染色理论在图论中占据着重要的位置 图的染色理论有很多分支 如 边染色 点染色 面染色和全染色等 其中研究最多 结果也较完善的就是图 的边染色 本文旨在讨论图的边染色的几个问题 即 染色 均匀边染色和分 数 染色 本文所考虑的图都是有限无向图 它们允许有重边 但没有环 图g 的一个 边染色就是把g 的边集划分为一些边不交的子集 为便于叙述 我们常常称这 些子集为颜色类 并给每个颜色类分配一个不同的颜色 设g 是与图g 的每 个顶点相关联的两个整值函数 并且对每一个移 y 回满足0 9 t g 的一个0 一因子 是g 的一个支撑子图 并且对所有的t v g 满足 g v 毋 口 如果图g 的一个边染色满足每个同色边导出子图都是图 g 的 个 吼 因子 则称该边染色是图g 的一个 g 一染色 特别地 0 1 染色 0 一染色 1 d 一染色和 g d 染色 对g 的每个顶点qd d 一 般分别被称为正常的边染色 染色 边覆盖染色和矿边覆盖染色 1 9 8 6 年 h a k i m i 和k a r i v 3 3 1 将正常的边染色推广到 染色并且得到了 很多有意义的结果 使g 有一个 染色所需的最少的颜色数被称为图g 的 色数 记作珥 g 显然 当对所有的t y g 都有 扣 1 时 染色问 题 即要确定任意图g 的舛 g 就简化为正常的边染色问题 h o l y e r 4 2 证明 正常的边染色问题是n p 完全的 即使限制到立方图也是如此 因此涵盖正常 的边染色问题为其子问题的 一染色问题也是n p 完全的 对一个图g 我们记 g 一州 m a x g g 2 册列州 m 1 其中f d 锄 1 为不小于d 的最小整数 在正常的边染色中 v i z i n g 7 9 的一个著名结果表明 任何简单图g 有 g g 或a g 1 根据这 山东大学博士学位论文 个结果 所有的简单图可以被划分成两类 若r g g 我们称简单图g 是第一类的 否则是第二类的 确定一个简单图是第一类还是第二类的问题被 称为关于正常边染色的分类问题 关于正常边染色的分类问题已经有了大量的 研究 特别重要的是 作为h a k i m i 和k a r i v 3 3 一个结果的推论 简单图的 染色有一个类似的结果 即对任意的简单图g 有 g s 舛 g a r g 1 成立 我们自然也可以考虑关于 染色的分类问题 若舛 g a g 我们 称图g 是 第一类的 否则是产第二类的 当所有的口 v a 均有 u 1 时 关于户染色的分类问题就简化为关于正常边染色的分类问题 本文讨论的另外一个问题是图的均匀边染色 设k 2 为一个整数 并且 c c i c 2 为一个颜色集 给定了图g 的用g 中k 种颜色的一个边染 色 对每个 y g 用c i 口 记与u 邻接的染颜色c i 1 i k 的那些边的 集合 如果图g 的用g 中k 种颜色的一个边染色对所有的1 i 的唯一顶点 则g 是 第一类的当且仅当 g 一1 0 是 一第一类的 结论1 4 设n 1 设g 是一个顶点数为2 n 且度d g a 的简单正则 v 山东大学博士学位论文 图 这里g j f 饭定对所有的u v a 均有 广 则g 是 一第 类 的当且仅当g w 是 一第一类的 其中 y g 显然 当对所有的v v c 都有 v 1 时 我们可以从结论l o 1 2 1 4 推 导出完全图和简单正则图关于正常边染色的分类问题中的那些结果 觅 t l 1 3 最后 在第二章中 我们考虑产临界图的性质 若简单图g 是 第二类 的 并且对每条边e e a 都有x g e 0 若g 是6 g 一可剥离 的 则 兄 回 6 g 我们考虑一类特殊的简单图 如果一个图g 的所有顶点可以用下述弱 j g 珈离法则相继被剥离掉 那么我们称g 是弱一6 g 一可剥离的 如果顶点 至多 还剩下一个这样的邻点t 满足t 矿 岛 并且t 的度仍然是j g 那么剥离 顶点u 对弱石 g 一可剥离简单图 我们得到如下漂亮的结果 结论2 0 设g 是一个简单图且d g 0 若g 是弱巧 g 可剽离的 则 兄 g 6 6 9 这个结果严格覆盖了结论1 9 也是王纪辉 张霞和刘桂真在 8 3 1 中一个结 果的推广 在第四章中 我们讨论图的分数户染色 n a k a n o 等提出了下列猜想 山东大学博士学位论文 猜想b n a k a n o 等 6 2 1 若g 是一个图 则 x a m a x a a a 1 a g 这里a g 2 蟛 嚅嚣丽 其中咿 2 我们给出了图的分数 一色数的确切值 结论2 1 对任意的图g x g m m a x g d a g 作为以上结果的一个推论 我们证明了猜想b 的分数形式 我们也可以从 结论2 1 推导出很多有意义的结果 另外 我们分别在第二 三 四章中给出了一些未解决的问题 关键词z 边染色 染色 均匀边染色 分数产染色 色数 分类问题 山东大学博士学位论文 t h e 一c o l o r i n ga n dt h ee q u i t a b l ee d g e c o l o r i n g o fg r a p h s z h a n g x i a s c h o o lo fm a t h s y s s c i s h a n d o n gu n i v j i n a n2 5 0 1 0 0 a b s t r a c t g r a p hc o l o r i n gt h e o r yh a sac e n t r a lp o s i t i o ni ng r a p ht h e o r y a m o n ga l l k i n d so fb r a n c h e so fg r a p hc o l o r i n gt h e o r y s u c ha se d g e c o l o f i n g v e r t e x c o l o r i n g f a c e c o l o r i n g t o t m c o l o r i n ga n d o n t h ee d g e c o l o r i n gi sg i v e nm o s ta t t e n t i o n a n dh a sm a n yp e d e c tr e s u l t s t h ea i mo ft h i st h e s i si st od i s c u s sr o m et o p i c s o ne d g e c o l o r i n gp r o b l e m s i e c o l o r i n g e q u i t a b l ee d g e c o l o r i n ga n df r a c t i o n a l c o l o r i n g i nt h et h e s i s a l lg r a p h sc o n s i d e r e d8 f i ef i n i t ea n du n d i r e c t e d t h e y g m a yh avemultiplee d g e sb u tn ol o o p sa ne d g e c o l o r i n go fg r a p h i sap a r t i t i o no fa l lt h e e d g e so fg i n t oe d g e d i s j o i n ts u b s e t s f o rt h ec o n v e n i e n c eo fd e s c r i p t i o n s w eo f t e n c a l lt h es u b s e t st h ec o l o rc l a 8 6 a n da s s i g nad i s t i n c tc o l o rt oe a c hc o l o rc l a s s l e t g fb et w oi n t e g e r v a l u e df u n c t i o n sa s s o c i a t e dw i t he a c hv e r t e xo fg r a p hgs u c h t h a to g f o re a c ht y g a g 一f a c t o r o fgi sas p a n n i n g s u b g r a p ho fg s u c ht h a t9 匠 f v f o ra l lt y g a0 一c o l o r i n g o fag r a p hgi sa ne d g e c o l o r i n gs u c ht h a te a c hs u b g r a p hi n d u c e db yt h ee d g e s c o l o r e dw i t ha 蛐ec o l o ri sa 玑 一f a c t o ro fg i np a r t i c u l a r 0 1 一c o l o r i n g 0 f c o l o r i n g 1 d c o l o r i n ga n d g d c o l o r i n g w h e r ed d v f o r e a c hv e r t e x t o fg a r eu s u a l l yc a l l e dp r o p e re d g e c o l o r i n g f c o l o r i n g e d g ec o v e r i n gc o l o r i n g a n d 俨e d g ec o v e r i n gc o l o r i n g r e s p e c t i v e l y i n1 9 8 6 h a k i m ia n dk a r i v 3 3 1g e n e r a l i z e dt h ep r o p e re d g e c o l o r i n gt ot h e c o l o r i n ga n do b t a i n e dm a n yi n t e r e s t i n gr e s u l t s t h em i n i m u mn u m b e ro fc o l o r s s u c ht h a tgh a sa nf c o l o r i n gi sc a l l e dt h ef c h r o m a t l ci n d e xo fga n dd e n o t e db y 舛 g o b v i o u s l y i f 口 1f o ra l l 口 y g t h e c o l o r i n gp r o b l e m w h i c hi st o 山东大学博士学位论文 d e t e r m i n e 巧 g o fa n yg r a p hg i sr e d u c e dt ot h ep r o p e re d g e c o l o r i n gp r o b l e m h o l y e r 4 2 p r o v c dt h a tt h ep r o p e re d g e c o l o r i n gp r o b l e mi s n p c o m p l e t e e v e n w h e nr e s t r i c t e dt ot h ec l a s so fc u b i cg r a p h s t h e r e f o r et h ef c o l o r i n gp r o b l e m l w h i c hc o v e r st h ep r o p c re d g e c o l o r i n gp r o b l e ma so n eo fi t ss u b p r o b l e r n s i sa l s o n p c o m p l c t e f o rag r a p hg w ew r i t et h a t g m y a x g d a n dz 1 a a m v a x g d 1 w h e r ef d 分 u 1i st h es m a l l e s ti n t c g e rn o ts m a l l e rt h a nd v f v i nt h ep r o p e r e d g e c o l o r i n g 8w e l l k n o w nr e s u l to fv i z i n gf 7 9 s a y st h a tf o ra n ys i m p l eg r a p hg r g a a o ra c 1 w i t ht h i sr e s u l t a l ls i m p l eg r a p h sa r en a t u r a u y p a r t i t i o n e di n t ot w oc l a s s e s w es a yt h a ts i m p l eg r a p hg i so fc l a s s1i fx 7 g g a n do fc l a s s2o t h e r w i s e t h ep r o b l e mo fd e c i d i n gw h e t h e ras i m p l eg r a p h i so fc l a s s1o rc l a s s2i sc a l l e dt h ec l a s s i f i c a t i o np r o b l e mo np r o p e re d g e c o l o r i n g s t h ec l a s s i f i c a t i o np r o b l e mo i lp r o p e re d g e c o l o r i n g sh a sb e e ni n t e n s e l ys t u d i e d s i g n i f i c a n t l y a sac o n s e q u e n c eo far e s u l t o fh a k i m ia n dk a r i vf 3 3 j t h e r ei sa s i m i l a rr e s u l to nf c o l o r i n g so fs i m p l eg r a p h s i e f o ra n ys i m p l eg r a p hg w e h a v ea s g 舛 g sa s a 1 n a t u r a l l y w ec a l lc o n s i d e rt h ec l a s s i f i c a t i o n p r o b l e mo n 户c o l o r i n g s w es a yt h a tg r a p hg i so ff c l a s s1i f 砖 g g a n do f 一c l a s s2o t h e r w i s e i f v 1f o ra l l y g t h ec l a s s i f i c a t i o np r o b l e m o nf c o l o r i n g si sr e d u c e dt ot h a to np r o p e re d g e c o l o r i n g s a n o t h e rt o p i d i s c u s s e di nt h i st h e s i si se q u i t a b l ee d g e c o l o r i n g so fg r a p h s l e t 知 2b ea l li n t e g e ra n dc c l c 2 c k b ea8 e to fc o l o r s g i v e na n e d g e c o l o r i n go fg w i t hkc o l o r si nc f o r 口 y g l e tc i v d e n o t et h e 融o f t h ee d g e si n c i d e n tw i t ht c o l o r e dw i t h 色 1sis c a l la ne d g e c o l o r i n go fg w i t h c o l o r si nc e q u i t a b l ei fl i n v i i e a v 1 1 1 v1 i f t h e ngi so f c l a s s1 矿a n dd 几冶矿g 一 妇o f c l a s s1 c o n c l u s i o n1 4l e tn 1 l e tgb e 口s i m p l er e g u l a rg r a p ho fo r d e r2 na n dd e g r e e d 硼h e r e g 鲍 l e t p 扣ra l l t y 回 t h e n g 螽0 1 f c l a s s 1 铲a n do r a v 矿g 一 i so 一c l a s s1 w h e r e 埘 y g c l e a r l y w ec a nd e d u c et h er e s u l t si nt h ec l a s s i f i c a t i o np r o b l e mo i lp r o p e r e d g e c o l o r i n g so fc o m p l e t eg r a p h so rs i m p l er e g u l a rg r a p h s s 能 1 1 1 3 f r o mo u r c o n c l u s i o n s1 0 1 2 1 4w h e nf v 1f o ra l lt y g f i n a l l y i nc h a p t e r2 骶c o n s i d e rt h ep r o p e r t i e so ff c r i t i c a lg r a p h s as i m p l e g r a p hg i sc a l l e df c r i t i c a li fgi so fy d a 2a n d 薪 g e 0 可g 妇6 6 3 p e e l a b l e t h e n 砭 g 6 6 3 w ec o n s i d e ras p e c i a lk i n do fs i m p l eg r a p h s w ec a l lag r a p hg w e a k i g 一 p e e l a b l e i fa l lt h ev e r t i c e so fg c a nb ei t e r a t i v e l yp e e l e do f fu s i n gt h ef o l l o w i n g w e a k 5 6 3 一p e e l i n go p e r a t i o n p e e lo f fav e r t e x 口 w h i c hh a sa tm o s to n er e m a i n i n g n e i g h b o rt s a t i s f i e dt h a tt v g 6 a n dt h ed e g r e eo ft i ss t i l l6 g f o rw e a k 6 6 3 一p e e l a b l es i m p l eg r a p h s w eo b t a i n8b e a u t i f u lr e s u l ta sf o l l o w s c o n c l u s i o n2 0l e tgb ens i m p l eg r a p hw i t hj 6 3 0 巧gi sw e a k 5 g p e e l a b l e t h e n 砭 g 6 6 3 t h i sr e s u l ts t r i c t l yc g y v e l c o n c l u s i o n1 9 a l s oi sa ne x t e n s i o no fap r e v i o u s r e s u l to fw a n g z h a n ga n dl i u s 3 i nc h a p t e r4 w ec o n s i d e rt h ef r a c t i o n a lf c o l o r i n go fg r a p h s n a k a n oe ta 1 p o s e dt h ef o l l o w i n gc o n j e c t u r e c o n j e c t t l r eb n a k a n oe ta 1 6 2 可gi s 口g r a p h t h e n x 6 3sm x g i r a g 1 砷们a i g 麟 赌器丽 饥碱矾 日 2 w eg i v et h ee x a c tv a l u eo ft h ef r a c t i o n a l c h r o m a t i ci n d e xo fag r a p h c o n c l u s i o n2 1 打a n yg r a p hg 圳q 2 缸 踩 出 a g 山东大学博士学位论文 a sac o n s e q u e n c eo ft h c a b o v er c s u l t w cp r o v ct h cf r a c t i o n a lv e r s i o no fc o n j c c t u r eb a l s o w ed e d u c em a n yi n t e r e s t i n gr c s u l t sf r o mc o n c l u s i o n2 1 i na d d i t i o n w ep r c s c n ts o m eu n s o l v e dp r o b l e m si nc h a p t c r s2 3 4 r e s p e c t i v c l y k e y w o r d s e d g e c o l o r i n g f c o l o r i n g e q u i t a b l cc d g e c o l o r i n g f r a c t i o n a l f c o l o r i n g c h r o m a t i ci n d e x t h ec l a s s i f i c a t i o np r o b l e m x l u 山东大学博士擎位论文 符号说明 图 顶点数为n 的完全图 集合s 的基数 不大于正的最大整数 不小于 的最小整数 g 的顶点集 g 的边集 g 的顶点数 g 的边数 g 中顶点口的度 正则图g 的度 g 的最小度 g 的最大度 g 中集合s 的邻点集 顶点u 的重度 g 的重度 由s 导出的g 的子图 s 与t 之间的边的集合 颜色集 x i x g 旧m m旧删 训 粥岬州胴粥聊g 山东大学博士学位论文 f v g v p x g x g g 砭 g g j g g a w g k g d 口 g c e o m o t m v a v w a 6 u g u o t p s 口 与g 中顶点 相关联的正整数 与g 中顶点 相关联的非负整数 g 中最小的f v g 的边色数 g 的 一色数 g 的分数户色数 g 的边覆盖色数 由度为6 a 的所有顶点导出的g 的子图 g 的核 g 的产核 g 的产核的顶点集 g 的扣核的顶点集 顶点口的产率 g 的 最大度 边e 的颜色 顶点 处染颜色o l 的所有边的集合 顶点口处颜色o t 可利用的次数 一染色中顶点 处所有可利用的颜色的集合 均匀边染色中顶点 处所有可利用的颜色的集合 起点为 的口扛交错途径 由所有染颜色n p 的边导出的g 的子图的含 的分支 顶点 处刚好出现f v 次的所有颜色的集合 n 山东大学博士学位论文 l 口 f 顶点口处刚好出现 口 一1 次的所有颜色的集合 在一个k 色均匀边染色中 顶点t 处刚好出现f 华1 次的颜 色的数目 扇 产匹配 0 一因子 g 的 匹配多面体 f 匹配f 的权 超图 子集族 向量 钾的点 超边关联矩阵 咒的乒层覆盖数 咒的分数覆盖数 t 的关联向量 超平面 恰好一个端点在s 中的所有边的集合 两个端点都在s 中的所有边的集合 半空间 向量a 中与e 对应的分量 f p f 咐 即 z x b 5 8 粥h 原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独立进 行研究所取得的成果 除文中已经注明引用的内容外 本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果 对本文的研究作出重要贡 献的个人和集体 均已在文中以明确方式标明 本声明的法律责任由本人 承担 论文作者签名 远趣 日期 丝 2 p 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子 版 允许论文被查阅和借阅 本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索 可以采用影印 缩印或其他复制手 段保存论文和汇编本学位论文 保密论文在解密后应遵守此规定 论文作者签名 j 鲞盘导师签名期 竺7 鱼垫 第一章绪论 图是建立各种数学模型的强有力的工具 图论有助于分析和解决如计算机 网络设计 城市规划和分子生物学等许多领域的问题 图的染色理论在图论中 占据着重要的位置 图的染色理论有很多分支 如边染色 点染色 面染色和 全染色等 其中研究最多 结果也较完善的就是图的边染色 本文旨在讨论图的边染色的几个问题t 简单图的 染色 简单图的均匀边 染色和图的分数 染色 在本章中 我们介绍一下本文的背景 在第1 1 节 我们给出本文所用到 的基本定义和符号 在第1 2 节 我们首先简要地回顾了边染色的历史 然后相 对完整地介绍了产染色 均匀边染色和分数 一染色的进展 1 1 基本定义和符号 在本文中 一个图g 始终代表一个有序三元组 y g s c a c g 该三元组 由一个有限非空的顶点集y g 一个有限的边集e g 与v a 不相交 和一 个关联函数妒g 组成 其中如给g 的每条边关联一个无序的g 的相异顶点 对 即 一个图g 是有限且无向的 它可以有重边 但没有环 如果e 是一 条边 t 和 是满足怡 e 伽的两个顶点 则称e 连接t 和弘并称顶点t i 和口是e 的端点 我们称没有重边的图为简单图 接下来 我们将着重介绍那 些在图论中不太熟知的定义和为方便本文表达所作的定义 对未定义的术语 请读者参阅文献 1 1 如果s 是一个集合 我们用l s l 记s 的基数 令v g l y g l 且 g i e g i 如果s 是一个集合 s l s 2 s k s u i 1 最 s 并且对所有的 1 f 0 时 一个图 可能没有 g 一染色 因而确定任一给定图 g 一染色的存在性是很重要的 9 一染色问题就是对任意给定的图g 确定该图 g 一染色的存在性 或者确 定g 存在 9 一染色所需颜色数的非平凡的上 下界 显然 图g 有一个 9 一染色当且仅当g 有一个 g 一因子分解 因此 g 一染色与 g 一因子分解之间有着密切的关系 从存在性的角度来看 9 一染色与 g 一因子分解是一致的 当前已有大景的研究在讨论 g 一染 色 9 一因子分解 的存在性和其性质 4 7 4 8 4 9 5 0 5 1 9 4 9 5 关于因子和 因子分解的更多结果见文献 1 4 1 2 2 6 4 4 4 6 5 3 5 4 5 6 6 8 1 虽然我们可以 将 g 一因子分解中已有的那些结果应用到 g 一染色中来 但必须明确指出 4 山东大学博士学位论文 的是 g 一染色问题与 g r 一因子分解问题是非常不同的 除了划分的存在 性这个共同的问题以外 前者侧重于研究一个图存在一个 g 一染色所需颜色 数的非平凡的上 下界 而后者侧重于研究 g r 因子分解的性质和 g 一因 子与 g 一因子分解之间的关系 另外 两个问题的研究方法也是完全不同的 接下来 我们将着重介绍本文要讨论的几类边染色问题的进展 即 染 色问题 均匀边染色问题和分数 染色问题的进展 我们已经知道 染色问 题是 g 一染色问题的一个子问题 稍后 我们会看到均匀边染色问题也是如 此 关于0 染色及其推广的其它进展 参见文献 5 9 7 4 8 2 9 0 9 1 1 2 1 图的 染色 1 9 8 6 年 h a k i m i 和k a r i v 3 3 将正常的边染色推广到了 染色 设g 是 一个图 是给每个顶点 v g 分配一个正整数 u 的一个函数 如前所 述 染色就是 0 一染色 即图g 的一个 染色是一个边染色使得每个 同色边集的边导出子图都是g 的一个 o 一因子 使g 有一个f 染色的最 少的颜色数被称为g 的户色敷 记作薪 回 使g 有一个 染色的最多的颜 色数 即e g 是平凡而没有意义的 我们称a s g m a x v e y g d v f v 是g 的产最大度 容易证实始 g a a g 显然 当所有的口 v c 都有 f v 1 时 要确定任意图g 的舛 g 的 染色问题就简化为正常的边染色 问题 h o l y e r 4 2 已证明正常的边染色问题是n p 一完全的 因而涵盖正常的边 染色问题为其子问题的 染色问题也是n p 完全的 事实上 早在1 9 7 5 年h i l t o n 3 5 1 就研究了对所有的u v g 有f v j 芝1 的图g 的 染色 并且确定了两类特殊图的 色数 h a k i m i 和k a r i v 3 3 1 研 究了图的 染色并获得了很多有意义的结果 其中大部分是正常边染色中经 典结果的推广 n a k a n o 等人0 8 2 得到了舛 g 的一个上界 z h o u 和n i s h i z e k i 9 9 1 证明 染色问题可在多项式时间内归结为正常的边染色问题 尽管他们给 出了简单图g 的 色数与按照某些法则从g 中构造的新图g 他的边色数之 间的一一对应关系 但是他们并没有对一般图给出这种一 对应关系 因而这 个问题本身就还有很多工作可以做 虽然z h o u 和n i s h i z e k i 9 9 1 的结论使得产 染色问题的境遇稍有些冷清 但是 染色问题的研究仍然是不可或缺的 还 有很多有意义的工作可以考虑 首先 染色有很强的应用背景 它在时间表 问题中有很多应用 如在计算机网络中的文件传输问题 参见文献 1 8 2 3 4 5 1 文件传输问题可以这样建立模型 假设每台计算机 都有一个有限的通信端口 5 山东大学博士学位论文 数 u 并且它传输每个文件所花的时间相同 在这些假定之下 使整个传输 过程的总时间最小化的时间表就对应着某个图的最少颜色数的一个 染色 其次 我们可以应用 染色中产生的方法来解决正常边染色问题 h i l t o n 3 5 h a k i m i 与k a r i v 3 3 n a k a n o 等人 6 2 的研究都作出了这样的贡献 在第2 2 2 4 2 5 和2 6 节 我们尝试得到了正常边染色中的一些经典结果 第三 我们 可以试图取得一些对正常边染色而言没有意义的更一般的结果 例如 对任意 给定的图g 我们可以考虑g 的 一色数与函数 之间的关系 在第2 3 节 我 们做了一个类似的工作 从文献 3 3 中 我们可以看到关于图的 一色数的一些上界 如v i z i n g 型 上界 o r e s h a n n o n 型上界等 特别地 我们在这里给出v i z i n g 型上界 定理1 2 4 h a k i m i k a r i v a a 设g 是一个图 则 g 弼 g m a 科x 亟 茜产 当所有的 v a 均有 v 1 时 v i z i n g 定理就可从定理1 2 4 中导 出 当g 是一个简单图时 每个 v a 都有p 1 因而下列推论成立 推论1 2 5 设g 是一个简单图 j l g x g m a x g i d 八v j1 g 1 自然地 所有的简单图都可根据它们的 色数将其划分成两类 更确切 地 如果薪 g g 则称g 是 第一类的 否则称g 是 第二类的 在第 二章中 我们着重讨论关于 一染色的分类问题 即确定一个简单图是 第一 类的还是产第二类的 我们应用各种各样的方法来处理不同的简单图类 另 外 我们也考虑了 临界图g 即f 第二类的连通的简单图g 满足对任意的 e s c 均有姊 g e x a g 成立 的性质 最近 刘桂真 侯建锋和蔡建 生 5 2 1 也研究了 临界图的性质 此外 一染色也被推广到了 驴染色 图g 的一个 酽染色就是g 的一 个 染色 使得对每对顶点 和 e w v 中至多有g w v 条重边染相同的颜 色 参见文献 6 3 6 4 6 6 6 山东大学博士学位论文 1 2 2 图的均匀边染色 均匀 的概念首先出现在点染色中 参见文献f l o 3 2 5 8 设k22 是一 个整数 c c l c 2 c k 是一个颜色集 绘定g 的用e 中k 种颜色的一个 边染色 对f y g 令岛 记与 关联的染颜色c f 1 i 七 的边的集合 给定g 的用c 中k 种颜色的一个边染色 如果对每个 v a 都有 q 0 l i q 1 1 vl c l q 口 l 成立 则m v 0 当i c l g 时 对 任意的 我们都有 l g f g d v cl o 成立 因此 如 果l c i g 或者l c i g 并且 圣w g 或者i c l a s a 并且 在 中至少还有一条边未染色 则m v o 下面 当提及m v n 或m v 时 9 山东大学博士学位论文 我们总是假定g 已经被给了一个部分边染色 注意 对g 的任意子图g 及所有的口 v c 总有豇 如 成立 现在 我们介绍图的 一染色中常用的两个工具 i 0 6 交错途径 设w 伽口l v k d b e 是两个相异的颜色 如果长度至少为一的途径 满足下列条件 则称其为n k 交错途径 a w 的边交错的染颜色d 和b 并且w 的第一条边染颜色b b 如果v o v k 则m v o d 1 如果珈 讥且l l 是奇数 则m v o 口 22 c 如果i 0 讥且1 w i 是偶数 则m 6 1 如果v o v k 且 i 是奇数 则m v k n 21 特别地 任何边交错染颜色 和b 的偶长的闭合途径 都是n 扛交错途 径 如果g 被给了一个部分 染色并且w 是g 中的一个小交错途径 那么 交换w 中边的颜色d 和6 就产生了g 的另一个部分 染色 这步操作被称为 切换 在w 被切换后 如果l 0 k 则m v i o 和m v l 6 保持不变 如果 w 不是偶长的闭合途径 则m v o 6 1 显然 w 被切换成一条6 m 交错途 径 我们用w a 6 伽 记以顶点如为起点的一条0 6 交错途径 i i 扇 设e o l l l 0 是g 的一条未染色的边 扇f 是和顶点 关联的相异边的一 个序列e o e 1 既 使得存在相异颜色的一个序列咖 n 1 o 女一z 满足下列条 件 a 和 b 这里t t j 被称为f 的轴心 佻是q 除 外的那个端点 0 i k b c f q 0 t 一l b c 龟 啦一1 1 k 当g 是一个简单图时 顶点1 0 是相异的 轮换扇f 就是对每个 i 0 k 一1 重新用颜色啦来染边岛 同时去掉边e k 的颜色o k l 如果g 被给了一个部分 一染色 那么轮换f 产生g 的另外一个部分 一染色 其中e 替换e o 成为未染色的边 一个极大的扇就是长度 不能再增加的扇 我们现在给出一个有用的引理 它在本章接下来的部分多次被用到 1 0 山东大学博士学位论文 引理2 1 1 设c 记可用来染简单图 g 的边的颜色的集合 假定e o w v o 是g 中一条未染色的边 并且图g 一 e o 已被用c 中颜色 染色 如果 或v o 的 每个邻点 3 都有m u o 那么我们可以用c 中的颜色来 染色e o 证明 不失一般性 我们可以假设1 o 的所有邻点 均有m v o 如果 m w n m v o 口 显然e 0 可以被吖 n 肘 中的任一种颜色来 染色 否则 构造相异颜色序列为咖 n l 一l 的一个扇f e o 8 l e 如果对 某个i 1 2 m 有m w n m v i o 则存在一个颜色 y m w n m v i 使得1 在顶点1 0 和仇可利用 通过轮换子扇p e o e l q 然后用颜色1 染 岛的方式 我们可以用颜色o o c 来产染色e 0 因此我们可以假设对所有的 i o 1 m 均有m n m v i o 此外 假设f 是一个极大的扇 显然 对f 有m d o 口l n 1 成立 设卢 m q m 由以上假设 f 不含有伊边 但恰好含有一 条 q 一边e j 1 0 jsm 一1 注意 o t 0 o t l o t r a 一1 互不相同 因而g 的任何n 卢一交错途径p w n 房t h 至多可能通过f 中的一条边 即a m 边e j 1 根据p 的终点的不同 我们分四种情况讨论 情况1 如果p 在 v a 埘 吩 终止 则先切换p 然后轮换 f e o e 1 i e f 1 现在p 在未染色的边e r a 1 t 的两个端点都是可利用的颜 色 因此我们可以用颜色p 来染 情况2 如果p 在t l 终止 则先切换p 然后轮换子扇f e o e l 8 j 现 在q 口 在未染色的边勺 w v j 的两个端点都是可利用的颜色 因此我们可 以用颜色d 来染e j 情况3 如果p 在吩终止 则先切换p 然后轮换子扇p 7 e o 8 l 岛 现在p 在未染色的边白 w v i 的两个端点都是可利用的颜色 因此我们可以用 颜色口来染8 f 情况4 如果p 在t l l 终止 则p 是一个闭合的o t 肛交错途径 并由 p 彗m 知i p j 是奇数 此外 m a 22 先切换p 然后轮换扇 f e o 8 l e i 现在口在未染色的边e m 的两个端点都是可利用 的颜色 因此我们可以用颜色p 来染e m 无论哪种情况 我们都可以用c 中的颜色来 染色e 0 口 山东大学博士学位论文 由以上引理 我们可以马上得到推论1 2 5 的一个证明 推论1 2 5 的证明 令q g m e y g 号券1 c c l c 2 白 g 因为 对任意的u v c 有 u g g d u 所以m v 0 总是成立 由引理2 1 1 我们可以通过一条接一条地染g 中的边的方式得到g 的用c 中q g 种颜色的 一个产染色 口 关于简单图的 染色 h a k i m i 和k a r i v 3 3 确定了二都图和所有口 v c 的f v 为偶数的图的 一色数 稍后在第2 3 节中 我们将从定理2 3 2 导出 h a k i m i 和k a r i v 在 3 3 1 中的那两个结果 最近 基于我们在第2 6 节给出的一个结果 即定理2 6 3 刘桂真 侯建锋 和蔡建生1 5 2 给出 第二类图关于它的 一临界子图的一个性质 并给出 一临 界图边数的上 下界 2 2 基于图的 核的 一第一类简单图的几个充分条件 首先 由引理2 1 1 我们很容易得到一个简单图是 一第一类图的一个充分 条件 令c c x c 2 c g 显然 当w g o 时 对所有的u v c 总有m v 0 再由推论1 2 5 我们得到以下结果 定理2 2 1 设g 是一个简单图 如果w g o 则g 是 第一类的 有了以上结果 我们仅需要考虑w g o 的情况 图g 的 一核就是由 w g 导出的g 的子图 记作g 如果对所有口 v g 都有 口 1 图g 的 核就是g 的核 即由度为a g 的所有顶点导出的g 的子图 记作g 简单图g 的产色数与g 的 一核有非常密切的关系 基于简单图g 的 核 我们得到了g 是 第一类图的一系列充分条件 定理2 2 2 设g 是一个简单图 如果g a 是一个森林 则g 是 一第一类的 1 2 山东大学博士学位论文 证明 令c c c 2 c a f g l 我们分三个阶段用c 中的 g 种颜色 来染g 的那些边 从而完成证明 假定g 中孤立顶点的数日是f 设v o u 1 t 2 是g 中所有孤立顶点的集合 我们设玩是e g 的一个边子 集 e 5 晶 晶 满足对每个i l 2 f 有晶 u i 越成立 其中 是g 中啦的任一个邻点 显然 簪w g 注意 顶点 i 呓 q 不必相异 我 们记e e o u e g a 阶段1 染e g 驴中的边 因为在子图g g e g e 中的每个顶点 的 率都小于 g 所 以总有m v d 成立 由引理2 1 1 我们可以得到g 的用g 中颜色的一个 染色 阶段2 染岛中的边 对任一未染色的边晶 撕 岛 1 i z 我们构造一个以啦为轴心的扇 芦 晶 e i e i 我们知道 趣是g 中的孤立顶点 因而n a 地 n y o g 一o 于是对地的每个邻点 总有u v 口 由引理2 1 1 通过一条一条地染晶中 的边 我们可以用g 中的颜色来 染色晶 阶段3 染e g a 中的边 用s 来记e g a 中已染色的那些边的集合 并用日来记s 中边的端点 集 我们按以下方式来染e g a 中的边 0 s o h 0 1 重复至s e g 1 1 如果对每条e 口 e g 么 s 均有钍簪h 和 岳h 则任取一条边 e o w v o e g s 否则转步骤1 3 1 2 构造以删为轴心的一个扇f e o l 按照引理2 1 1 中描述的方法 来染句 令s s u f e d h 曰u 蛳 如果s 曰 g 么 转步骤1 1 1 3 选择e o w v o e e g s 使得t i 譬h 且v o h 转步骤1 2 首先 我们断言t 按以上描述的染色方法 不会出现 h 并且v o h 的 边e o w v o e g s 佣反证法 显然 t l 伽属于g 的同一分支 再 由步