《关于一些图的定向染色》由会员分享，可在线阅读，更多相关《关于一些图的定向染色（46页珍藏版）》请在金锄头文库上搜索。
1、 i 罐 纛 旁 鹣抄 l l ， q 分类号：0 15 “ 1 芎 密级： 论文题目： 单位代码：1 0 4 2 2 学号：2 0 08JJ 1 ) - I 紊力孥 硕士学位论文 S h a n d o n gU n i v e r s i t yM a s t e r sT h e s i s 美j 一咝国锦建向渌包 阶肿以G f ) H j 呼如G 岬心 作 者1 垒卑一专 业墨聋塑复主壑擅】也 导 师曼堑良数控一一一 合作导师 2 0s 1 年弓月加日 久I 纛篱。 f III I I II r l I I r l lrr i l lI I If f ll 哪 Y 19 3 7 8 3
2、 0 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究所取得的成果除文中已经注明引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写过的科研成果对本论文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明本声明的法律 责任由本人承担 论文作者签名： 堇查兰 日期I2 Q f 2 ，互：z 口一一 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其
3、他复制手段保 存论文和汇编本学位论文 ( 保密的论文在解密后应遵守此规定) 论文作者签名：翌盔埠 导师签名：数日期：出加 山东大学硕士学位论文 目录 中文摘要I 英文摘要I I I 符号说明I 第一章前言1 1 1 基本概念I 1 2 图的染色理论4 1 3 图的定向染色理论5 1 4 研究内容和章节安排7 第二章几类退化图的定向染色9 2 1 预备知识及引理9 2 2 定理及证明1 l 第三章双外平面图和特殊平面图的强定向染色1 5 3 1 双外平面图的强定向染色1 5 3 2 特殊平面图的强定向染色1 7 第四章定向染色的推广2 1 第五章总结2 3 参考文献2 5 致谢2 9 一I 一
4、山东大学硕十学位论文 C O N T E N T S C h i n e s eA b s t r a c t 。I E n g l i s hA b s t r a c t I I I N o t a t i o n s I C h a p t e r1 I n t r o d u c t i o n 1 1 1 B a s i cD e f i n i t i o n s 1 1 2 T h e o r e mo fG r a p hC o l o r i n g 4 1 3 T h e o r e mo f G r a p hO r i e n t e dC o l o r i n g
5、5 1 4 C o n t e n d sa n dC h a p t e r sA r r a n g i n g 7 C h a p t e r2O r i e n t e dC o l o r m go fS o m eD e g e n e r a t eG r a p h s 。9 2 1 P r e h m i n a r i e sa n dL e m m a s 9 2 2 T h e o r e m sa n dP r o o f s 1 1 C h a p t e r3S t r o n gO r i e n t e dC o l o r i n go fD o u b l
6、 e - o u t e rP l a n a rG r a p h sA n d S p e c i a lP l a n a rG r a p h s 1 5 3 1S t r o n gO r i e n t e dC o l o r i n go fD o u b l e - o u t e rP l a n a rG r a p h s 1 5 3 2S t r o n gO r i e n t e dC o l o r i n go fS p e c i a lP l a n a rG r a p h s 1 7 C h a p t e r 4I m p r o v e m e n
7、 to fO r i e n t e dC o l o r i n g 2 1 C h a p t e r 5C o n c l u s i o n s 2 3 R e f e r e n c e s ：1 5 T h a n k s 2 9 一I I 一 山东大学硕十学位论文 关于一些图的定向染色 于本娟 ( 山东大学数学学院，济南，2 5 0 1 0 0 ) ( 指导老师：吴建良教授) 中文摘要 一个定向图就是指一个无向图的定向，即给它的每条边一个方向本文所说 的定向图都是简单的有向图，即无环或无重弧的有向图对一个定向图，我们用 y ( G ) 、A ( G ) 、6 ( G ) 、a (
8、 a ) 分别表示图G 的点集、弧集、最小度和最大度，d ( v ) 表示点口的度如果扒v 是图G 中两个相邻的点，用仳u 表示从牡到V 的弧G 的阶数即为图G 的点数 假设G 和日是两个有向图，那么从G 到日的一个同态是指一个作用在v ( a ) 到V ( H ) 的一个映射妒，满足：( z ，Y ) E ( a ) 号( 妒( z ) ，妒( 秒) ) E ( 日) ，则称日是G 的一个目标图，记作G 日 图日的一个舡正常染色是指将图日的点集分成k 个子集( 颜色类) 的一个 剖分，且满足任何两个相邻的点不属于同一个子集，相当于从日到完全图纸的一 个同态，那么图日的染色数x ( H ) 就
9、可以定义为H 的所有肛J 下常染色中最小的 k ，即k 满足日一玩，日讲峨一1 一个定向图G 的一个缸定向染色是指将点集v ( a ) 分成k 个子集( 颜色类) 的一个剖分，且满足：( 1 ) 任何两个相邻的点不属于同一个子集；( 2 ) 任何两个子集 之间的弧都有相同的方向同样定向图G 的定向色数( H ) 可以定义为G 的所有 “定向染色中最小的k ，即k 为满足G 一日的所有定向图日的最小阶，也就是G 的所有目标图的最小阶对于一个无向图，它的定向色数是指它的所有定向中的最 大的定向色数其中强定向染色是指目标图为C a y l e y 图的定向染色，强定向染色 数记为舶( 日) 关于图的
10、定向染色，K o s t o c h k a 和S o p e n a 等人做了图的无圈定向色数的研究， R o b e r tS a m a l 研究了平面图的强定向染色，O c h e m 研究了无三角平面图的定向染 色，B o r o d i n 等人研究了给定围长的全体平面定向图，并在2 0 0 4 年发表了围长不限 的稀疏图之间的同态问题的文章，同时对一个图的最大平均度与定向色数之间的 一I 一 山东大学硕士学位论文 关系也作了深入研究 本文主要研究几类退化图，双外平面图和特殊平面图的强定向染色问题，得到 如下结果： 定理1 令G 为2 一退化图，则舶( G ) 7 定理2 令G 为
11、3 - 退化图，则( G ) 1 9 定理3 令G 为4 一退化图，则( G ) 6 7 定理4 令G 为双外平面图，且G 不同构于P ，则始( G ) 1 9 ，( P ) 6 7 定理5 设G 为平面图，且G 不舍4 7 圈，则池( G ) 1 9 对上述问题本文主要是运用可约化的方法和权值重新分配的方法来证明的 在本文的最后我们对定向染色的定义进行了推广，定义了一种新的染色一有 向2 路染色 令m 为大于等于1 的整数定向图G 的一个有向僻路k 染色，是指 一个映射，：V ( G ) H 1 ，2 ，七 ，满足：( 1 ) 对任意的两个点z ，Y ，如果 1 d ( x ，Y ) m ，
12、则f ( x ) ，( 耖) ；( 2 ) 任何两个子集之间的弧都有相同的方向定 向图G 的有向T t - 路色数x m ( G ) 是指G 的所有有向r n - 路k 染色，的最小的 k 那么无向图G 的有向m 路色数x m ( G ) 是它的所有定向图的有向胁路色数 X 仇( G ) 中的最大值当m = 2 时，即为有向2 - 路染色 根据H a l i n 图的有向2 路色数小于等于7 的结论，我们对2 退化图的有向2 路色数作了猜想： 猜想如果G 是一个2 - 退化图，则x 2 ( G ) 5 关键字：双外平面图；退化图；定向染色；强定向染色；有向2 路染色 一I I 一 山东大学硕士
13、学位论文 O r i e n t e dC o l o r i n go fS o m eG r a p h s B e n j u a nW a n g ( S c h o o lo fM a t h e m a t i c s ，S h a n d o n gU n i v e r s i t y , J i n a n ，2 5 0 1 0 0 ) ( S u p e r v i s o r ：J i a n l i a n gW u ) A B S T R A C T A no r i e n t e dg r a p hi sa no r i e n t a t i o no fa nu n d i r e c t e dg r a p h ，o b t a i n e db ya s s i g n - i n gt oe v e r ye d g eo n eo ft h et w op o s s i b l eo r i e n t a t i o n s O r
