（运筹学与控制论专业论文）双外平面图的点染色.pdf

山东大学硕士学位论文 双外平面图的点染色 摘要 图染色问题是图论研究中的重要问题之一和热点之一，有重大的理论价值和 应用背景。双外平面图是一种新的特殊的平面图，所有点出现在两个面的边界上 的平面图，称为双外平面图。但到目前为止，关于这一特殊的平面图的很多问题 还有待解决，本论文主要双外平面图的点染色问题。g 的一个k 顶点染色是指七种 颜色1 ，2 ，k 对于g 的各顶点的一个分配，使g 为k 可染色的数k 的最小值， 称为图g 的点色数z ( g ) 。 本论文在参考了双外平面图已有结果的基础上考虑双外平面图的点染色的问 题，具体做了以下工作： 1 讨论了= 2 、= 3 时，磊= 2 和厄= 3 。 2 = 4 时，( 1 ) 图g 中有1 个圈及剖分点的点色数，得到( i ) 当顶点总数 为6 胛时，不管加几个剖分点，都有矶= 3 。( i i ) 当顶点总数为6 n + 2 时，加一个 剖分点，都有氛= 3 ，加2 个及以上剖分点时，剖分点加在标号为2 对应的边上时， 有厄= 3 ；剖分点加在标号为1 ，3 对应的边上时，有磊= 4 ( ) 当顶点总数为6 n + 4 时，加一个剖分点，都有苁= 3 ，加2 个及以上剖分点，剖分点加在标号为3 对应 的边上时，有乞= 3 ；剖分点加在标号为l ，2 对应的边上时，有厄= 4 。( 2 ) 图g 中有1 条路及 f 6 疗+ l 剖分点的点色数，得到( i ) 不加剖分点时，当顶点数为 6 n + 20 = l ，2 ，) 时， 【6 n + 3 磊= 4 其他情况时，航= 3 ( i i ) 当磊= 4 时，当在相同面上两端的顶点标号冲突 时，如果剖分点加在这个标号相对的边上时，仍然有航= 4 ，加在其他边上时，有 氖= 3 。 2 山东大学硕士学位论文 ( 3 ) 图g 中有2 条路及剖分点的点色数，得到( i ) 两条路不加剖分点时，有2 种情况磊= 4 ，其他情况都是磊= 3 ：( i i ) 两条路加1 个剖分点时，有篇= 3 。( 4 ) 图g 中有3 及以上条路的点色数，得到3 条路进行染色都可以用3 种颜色，即 磊= 3 。 3 = 5 时，讨论了怎样转化为a = 4 的情况。 关键词：双外平面图；点染色；点色数；最大度；圈 山东大学硕士学位论文 a b s t r a c t t h ec o l o r i n gp r o b l e mo fg r a p h si ng r a p ht h e o r yi so n eo ft h ei m p o r t a n ti s s u e sa n d o n eo ft h eh o ts p o t s ，t h e r eh a v es i g n i f i c a n tt h e o r yv a l u ea n da p p l yb a c k g r o u n d t h e d o u b l e - o u t e rp l a n a rg r a p hi san e ws p e c i a lp l a n a rg r a p h a l lo ft h ev e r t e xa p p e a rt w oo f t h eb o r d e ro ft h ep l a n a rg r a p h ，c a l l e dd o u b l e o u t e rp l a n a rg r a p h b u ts of a r , a b o u tm a n y p r o b l e mo ft h i ss p e c i a lp l a n a rg r a p ht ob er e s o l v e d t h i sp a p e rw i l lm a j n l yd i s c u s st h e v e r t e xc o l o r i n gp r o b l e mo fd o u b l e o u t e rp l a n a rg r a p h ak v e r t e xc o l o u r i n go fgi sa l l a s s i g n m e n to fkc o l o u r s ，1 ，2 ，k ，t ot h ev e r t i c e so fc t t h ec h r o m a t i cn u m b e ro fg i st h e m i n i m u n lkf o rw h i c hgi sk - c o l o u r a b l e 。 o nt h eb a i s i so ft h er e s u l to fd o u b l e - o u t e rp l a n a rg r a p h ，t h i sp a p e rc o n s i d e r e dt h e v e r t e xc o l o u r i n gp r o b l e mo ft h ed o u b l e o u t e rp l a n a rg r a p h s p e c i f i ct od ot h e f o l l o w i n gw o r k ： 1 d i s c u s sw h e na = 2 、= 3 ，t h e r eh a v e 厄= 2a n d 磊= 3 2 w h e n = 4 ，( 1 ) t h ec l l r o m a t i cn u m b e ro fgh a v eac i r c l ea n ds u b d i v i s i o no f v e r t e x ，w eg e t ( i ) w h e nt h et o t a lv e r t e xi s6 n ，i ns p i t eo fa d d sh o wm a n ys u b d i v i s i o no f av e r t e x ，i ti s z ，= 3 ( i i ) w h e nt h et o t a lv e r t e xi s6 n + 2 ，a d d sas u b d i v i s i o no fv e r t e x ， i ti s 磊= 3 ，a d d st w oo rm o r es u b d i v i s i o no fv e r t i c e s ，s u b d i v i s i o no fv e r t e xa d d st h e e d g eo fl a b e l i n g2 ，i ti s 五= 3 ；s u b d i v i s i o no fv e r t e xa d d st h ee d g eo fl a b e l i n g1 , 3 ，i t i s 磊= 4 ；( i i i ) w h e nt h et o t a lv e r t e xi s6 n + 4 ，a d d sas u b d i v i s i o no fv e r t e x ，i ti s 乞= 3 ，a d d st w oo rm o r es u b d i v i s i o no fv e r t i c e s ，s u b d i v i s i o no fv e r t e xa d d st h ee d g eo f l a b e l i n g3 ，i ti s 以= 3 ；s u b d i v i s i o no fv e r t e xa d d st h ee d g eo fl a b e l i n g1 , 2 ，i ti s 厄= 4 ；( 2 ) t h ec h r o m a t i cn u m b e ro fgh a v eap a t ha n ds u b d i v i s i o no fv e r t e x ，w e g e t ( i ) i tn oa d ds u b d i v i s i o no fv e r t e x ，w h e nt h et o t a lv e r t e xi s 3 山东大学硕士学位论文 f6 刀+ l 6 n + 2 0 = 1 ，2 ，) ，i ti s 磊= 4 ；o t h e r w i s e 磊= 3 ( i i ) w h e n 磊= 4 ，t h et w o l6 阼+ 3 e n d sv e r t e xl a b e l so ft h es a m ef a c ei sc o n f l i c t ，i fs u b d i v i s i o no fv e r t e xa d d st h er e l a t i v e e d g eo ft h i sl a b e l ，i ti sa l s o 磊= 4 ，a d d so t h e re d g e s ，i ti s 航= 3 ( 3 ) t h ec h r o m a t i c n u m b e ro fgh a v et w op a t h sa n ds u b d i v i s i o no fv e r t e x ，w eg e t ( i ) t w op a t h sh a v en o s u b d i v i s i o no fv e r t e x ，t w os i t u a t i o ni s 磊= 4 ，t h eo t h e rs i t u a t i o ni s 六= 3 ；( i i ) t w o p a t h sa d d sas u b d i v i s i o no fv e r t e x ，i ti s 苁= 3 。( 4 ) t h ec h r o m a t i cn u m b e ro fgh a v e t h r e eo rm o r ep a t h s ，w eg e tt h e r eh a v et h r e ec o l o u r st oc o l o u r , i ti s 航= 3 3 w h e na = 5 ，d i s c u s s e dh o wt ot r a n s l a t ei n t oa = 4 。 k e y w o r d s ：d o u b l e o u t e rp l a n a rg r a p h ，v e r t e xc o l o r i n g ，c h r o m a t i cn u m b e r ，m a x i m u m d e g r e e ，c i r c l e 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：多】芝i 受日期：兰! 里矗! ! 旦2 鱼8 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：童! ) 士盈爱导师签名：兰蕉鱼 日 期： 山东大学硕+ 学位论文 第一章绪论 1 1 基本概念与符号 本学位论文主要考虑双外平面图的点染色的问题，我们首先将引进一些概念 和符号，这些符号和概念将贯穿全文对一本章没给出的符号和概念，我们会在后 面适当的地方给出对于那些文中未给出的符号和概念，可以在中找到。 本文用矿( g ) 、占( g ) 、f ( g ) 、a 分别表示图g 的点集、边集、面集和最大度。 在平面图g 中，我们称面与其边界上的点或边相关联；如果两个面共同关联于同 一条边，称这两个面相邻。平面图g 的点染色是使得y ( g ) 中任何两个相邻的顶点 染不同颜色。图g 的色数磊是指使g 中任何相邻顶点均染不同颜色的最少颜色 数。图g 的顶点，的度叱( v ) 是指g 中与关联的边的数目，每个环算作两条边，用 8 ( a ) 和a ( g ) 分别表示g 的顶点的最小度和最大度。偶图是指一个图，它的顶点集 可以分解为两个子集x 和】，使得每条边都有一个端点在x 中，令一个端点在】， 中。平面图g 是指一个图能画在平面上使得它的边仅在端点相交。 定义l ：如果一个图是可嵌入平面的，且它所有顶点出现在无穷面的边界上， 称该图为外平面图。无穷面称为外面，其余面称为内面。 定义2 ：所有点出现在两个面的边界上的平面图，称为双外平面图，我们把这 两个面称为外面。 用同样的方法，我们可以定义3 一外平面图、4 一外平面图、5 - # b 平面图，等等。 根据双外平面图的定义：任何一个外平面图都可以认为是一个双外平面图， 因为我们可以取无穷面和任何一个内面作为双外平面图的两个外面。以下我们总 是假设双外平面图已经嵌入到平面上。且所有点出现在两个面的边界上。 引理1 ：若g 是连通的简单图，并且它既不是奇圈，又不是完全图，则五a 。 引理2 ：g 为偶图磊= 2 。 引理3 ：对任意图g ，有苁a + 1 。 5 山东大学硕士学位论文 引理4 ：按三角形标号，双外平面图最多4 色。 1 2 双外平面图的的研究概况与本文的研究工作 双外平面图是在平面图的基础上来定义的，因此平面图的一些结果可以对双 外平面图的研究有重要指导意义。平面图是指一个图能画在平面上使得它的边仅 在端点相交。在平面图中，我们称面与其边界上的点，边相关联：如果两个面共同关 联于同一条边，称这两个面相邻。平面图染色有1 3 情况的讨论，而外平面图则刚 刚起步。 双外平面图是山东大学数学与系统科学学院的吴建良教授定义的，是指所有 点出现在两个面的边界上的平面图。在有了这个定义之后，围绕双外平面图的研 究就开始了，双外平面图的边染色方面，孔立们证明了对最大度至少为6 的双外 平面图是第一类的。双外平面图的边面染色方面，孔立n 们证明了对于最大度至少 是6 的双外平面图，有x e f ( g ) a ( g ) + l ，其中( g ) 是g 的最大度。设g 是一个双 外平面图，v ( g ) ，e ( g ) ，f ( g ) 分别为双外平面图g 的点集，边集和面集。g 的全色数 x t ( g ) 是使得v ( g ) u e ( g ) 中的任意两个相邻或相关联的元素间均染不同颜色的最 少颜色数。双外平面图的全染色方面，孔立n 3 1 证明了对最大度为6 的双外平面图， 全色数是( g ) + 1 ，其中( g ) 为g 的最大度数。 本学位论文主要考虑双外平面图的点染色的问题，具体做了以下工作： 1 = 2 时，g 为偶图磊= 2 。 2 = 3 时，由定理l 可知，厄= 3 。 3 a = 4 时，分了几种情况进行讨论 ( 1 ) 图g 中有1 个圈及剖分点的点色数，得到( i ) 当顶点总数为6 即时，不 管加几个剖分点，都有矶= 3 。( i i ) 当顶点总数为6 n + 2 时，加一个剖分点，都 有磊= 3 ，加2 个及以上剖分点时，剖分点加在标号为2 对应的边上时，有舭= 3 ； 剖分点加在标号为1 ，3 对应的边上时，有氙= 4 ( i i i ) 当顶点总数为6 n + 4 时， 加一个剖分点，都有厄= 3 ，加2 个及以上剖分点时，剖分点加在标号为3 对应的 边上时，有磊= 3 ；剖分点加在标号为1 ，2 对应的边上时，有厄= 4 6 山东人学硕士学位论文 ( 2 ) 图g 中有1 条路及剖分点的点色数，得到( i ) 不加剖分点时，当顶 l 6 n + l 点数为 6 n + 2仰= l ，2 ，) 时，磊= 4 其他情况时，鼠= 3 ( i i ) 磊= 4 时，当在 【6 n + 3 相同面上两端的顶点标号冲突时，如果剖分点加在这个标号相对的边上时，仍然 有厄= 4 ，加在其他边上时，有磊= 3 。 ( 3 ) 图g 中有2 条路及剖分点的点色数，得到( i ) 两条路不加剖分点时， 有2 种情况磊= 4 ，其他情况都是磊= 3 ：( i i ) 两条路加1 个剖分点时，有磊= 3 。 ( 4 ) 图g 中有3 及以上条路的的点色数，得到3 条路进行染色都可以用3 种 颜色，即厄= 3 。 4 a = 5 时，讨论了怎样转化为a = 4 的情况。 7 山东大学硕士学位论文 第二章最大度为4 的双外平面图的点染色 2 1图g 中只有1 个圈及剖分点的点色数 定理l ：图g 中的结构是一个圈时，( 1 ) 当顶点总数为6 刀时，不管加几个剖 分点，都有磊= 3 。( 2 ) 当顶点总数为6 n + 2 时，加一个剖分点，都有厄= 3 ，加 2 个及以上剖分点时，剖分点加在标号为2 对应的边上时，有z = 3 ；剖分点加在 标号为1 ，3 对应的边上时，有厄= 4 ( 3 ) 当顶点总数为6 n + 4 时，加一个剖分点， 都有磊= 3 ，加2 个及以上剖分点时，剖分点加在标号为3 对应的边上时，有磊= 3 ； 剖分点加在标号为1 ，2 对应的边上时，有疋= 4 。 若图g 中的结构是一个圈，即d ( v ) = 4 v v 矿。 若顶点总数是6 的倍数，则图g 的点色数磊= 3 ，顶点总数是6 力+ 2 和6 n + 4 时 磊= 4 ，下面对6 n + 2 和6 n + 4 加剖分点进行讨论： ( 1 ) 对于6 n + 2 情况，我们以顶点总数为8 的图进行讨论，结构是： 加一个剖分点， 有磊= 4 。 当确定完一个剖分点后，我们给该图的顶点进行标号，把剖分点所在的边对 应的顶点标为1 ，然后按顺时针方向标2 ，3 ，1 ，如上图所示。 8 山东大学硕士学位论文 我们继续加第二个剖分点，第二个剖分点的所加的位置有3 种情况，分别是标号 为1 ，2 ，3 所对应的边上，我们作图如下： 我们对上述的图进行重新标号，可以得到第二个剖分点加在标号为2 对应的边上 时，有氙= 3 ，如图： 2 3 2 当第二个剖分点加在标号为1 ，3 对应的边上时，有矶= 4 。 对于6 n + 2 的其他图形，也可以按照上述原则进行标号，可得：加2 个及以上 剖分点时，剖分点加在标号为2 对应的边上时，有厄= 3 ；剖分点加在标号为1 ， 3 对应的边上时，有疋= 4 。 ( 2 ) 对于6 n + 4 情况，我们以顶点总数为1 0 的图进行研究，结构是： 都有 9 山东大学硕士学位论文 当确定完一个剖分点后，我们给该图的顶点进行标号，把剖分点所在的边对 应的顶点标为1 ，然后按顺时针方向标2 ，3 ，l ，如上图所示。 我们继续加第二个剖分点，第二个剖分点的所加的位置有3 种情况，分别是标号 为1 ，2 ，3 所对应的边上，我们作图如下： 4 ( 1 ) 4 ( )4 ( 1 ) 2 2 我们对上述的图进行重新标号，可以得到第二个剖分点加在标号为3 对应的边上 时，有磊= 3 ，如图： 2 2 1 当第二个剖分点加在标号为1 ，2 对应的边上时，有氛= 4 对于6 n + 4 的其他图形，也可以按照上述原则进行标号，可得：加2 个及以上 剖分点时，剖分点加在标号为3 对应的边上时，有以= 3 ；剖分点加在标号为1 ， 2 对应的边上时，有厶= 4 。 综上所述，图g 中的结构是一个圈时，( 1 ) 当顶点总数为6 n 时，不管加几个 剖分点，都有磊= 3 。( 2 ) 当顶点总数为6 n + 2 时，加一个剖分点，都有磊= 3 ， 加2 个及以上剖分点时，剖分点加在标号为2 对应的边上时，有五= 3 ；剖分点加 在标号为1 ，3 对应的边上时，有航= 4 ( 3 ) 当顶点总数为6 n + 4 时，加一个剖分 点，都有磊= 3 ，加2 个及以上剖分点时，剖分点加在标号为3 对应的边上时，有 磊= 3 ：剖分点加在标号为1 ，2 对应的边上时，有以= 4 。 l o 山东大学硕+ 学位论文 2 2图g 中只有1 条路及剖分点的点色数 f 6 n + l 定理2 ：( 1 ) 不加剖分点时，当顶点数为 6 n + 2o = 1 ，2 ，) 时，疋= 4 ，其 【6 n + 3 他情况时，磊= 3 。( 2 ) 磊= 4 时，当在相同面上两端的顶点标号冲突时，如果剖 分点加在这个标号相对的边上时，仍然有磊= 4 ，加在其他边上时，有磊= 3 。 对于一条路从右向左按照1 2 3 进行标号，有以下结构： 133123 2 212 23 312 4231 继续往下画时，第1 0 种结构和 42 12 31 31231 31 就一样了，从上边 1 2 的9 种结构来看第1 、2 、3 、4 、5 这5 种结构都可以用3 种颜色来染色，第6 、7 、 8 这3 种结构都要用4 种颜色来染色，第1 0 种和第3 种，第1 1 种和第4 种，第 1 2 种和第5 种，第1 3 种和第6 种都可以用一样的颜色来染色，第6 、7 、8 这3 种结构对应的顶点数为7 、8 、9 。 山东大学硕士学位论文 由此可以归纳出当顶点数为 6 n + 2= l ，2 ，) 时，磊= 4 ， i6 疗+ l 1 6 终+ 3 其他情况时，磊= 3 。 1 2 对于厄= 4 的3 种情况，我们加剖分点来看看需要几种颜色能染。 423 1 ( 1 ) 对于 312 加入1 个剖分点有如下情况： 3123123 12 3 423 3 423 我们可以重新进行进行标号，有的可以用3 种颜色进行染色，结果如下： 312 山东大学硕士学位论文 323 4231 213 其中有2 种情况加入1 个剖分点后仍然需要4 种颜色来染，这2 种情况都是 剖分点加在标号为1 的点对应的边上，因为在相同面上l 的标号冲突。 42 31 况 ( 2 ) 对于 2 ( 1 ) 31 2 1 ( 4 )23 加入1 个剖分点有如下情 2 ( 1 ) 31 2 1 ( 4 )2311 ( 4 )231 1 ( 4 )23 1 3 山东大学硕士学位论文 我们可以重新进行进行标号，有的可以用3 种颜色进行染色，结果如下： 2 ( 1 ) 312 213 2 ( 1 ) 312 1 ( 4 )2 3 11 ( 4 )2 3 1 其中有6 种情况加入1 个剖分点后仍然需要4 种颜色来染，这6 种情况都是 剖分点加在标号为1 和2 的点对应的边上，因为在相同面上1 和2 的标号都冲突。 31231 ( 3 ) 对于 1 4 加入1 个剖分点有如下情况 2 ( 4 ) 31 2 2 ( 4 ) 312 2 ( 4 ) 312 3123 1 山东大学硕士学位论文 3123 13 12313123 1 我们可以重新进行进行标号，有的可以用3 种颜色进行染色，结果如下： 2 ( 4 )312 2 ( 4 ) 312 2 12313123132131 其中有4 种情况加入1 个剖分点后仍然需要4 种颜色来染，这4 种情况都是 剖分点加在标号为2 的点对应的边上，因为在相同面上2 的标号都冲突。 由上边的3 种磊= 4 加一个剖分点的结果，有以下结论：当在相同面上两端的 顶点标号冲突时，如果剖分点加在这个标号相对的边上时，仍然有磊= 4 ，加在其 他边上时，有氖= 3 。另在第8 种结构时，当剖分点加在相同面上两端的顶点标号 不冲突的边上，仍然有乞= 4 。 综上所述，( 1 ) 不加剖分点时，当顶点数为 6 n + 2= 1 ，2 ，) 时，氟= 4 ； l6 ，z + l 1 6 刀+ 3 山东大学硕士学位论文 其他情况时，磊= 3 。( 2 ) 磊= 4 时，当在相同面上两端的顶点标号冲突时，如果 剖分点加在这个标号相对的边上时，仍然有磊- 4 ；加在其他边上时，有磊= 3 。 2 3 图g 中只有2 条路及剖分点的点色数 定理3 ：( 1 ) 两条路不加剖分点时，有2 种情况二= 4 ，其他情况都是磊= 3 。( 2 ) 两条路加1 个剖分点时，有航= 3 。 对于一条路从右向左按照1 - 2 3 进行标号，有6 种结构( 第7 种结构和第一 种一样) 盟莅 2 212 麓- t 23 3 1 2 31 2 2 第二条路也按照1 2 3 进行标号，两边的4 个顶点标号一定有以下6 种情况： 将第一条路的6 种情况插入到第二条路中，并对第一条路重新进行标号，可 得以下结论。 1 6 山东大学硕士学位论文 插入 插入 插入 1 2 123 21 2 2 v = 3 3 有以下结果： 123 231 磊= 3 121 213 磊= 3 2 1213 v 232 2 v = 3 3 有以下结果： 13 21 32 24 1 磊= 4 121 212 磊= 3 1213121 2 v 231 磊= 3 1231 v 2 13 磊= 3 2 有以下结果： v 23 1 氛= 3 12 31 v 212 2 v = 3 213 磊= 3 1232 v 213 磊= 3 1 7 山东大学硕士学位论文 插入 插入 插入 1 8 12 墨 12131212 21 3 2 氛= 3 1312 n 2123 n 21 31 2 v = 3 1231 n 23 13 乞= 3 有以下结果： n 21 31 氛= 3 1231 n 2 312 乞= 3 13 21313212 w 2132 2 131 磊= 3 123 12 w 2 12 3 疋= 3 23 磊= 3 w 23 23 磊= 3 有以下结果： 1 3l 23 1 3 12 3 21 23 2 磊= 3 12 312 v 231 2 3 磊= 3 212 31 氛= 3 1 2 131 叭 2132 3 2 v = 3 有以下结果： w 2131 磊= 3 2432 磊= 4 1 2312 w 2 3121 氛= 3 13121 212 32 磊= 3 二瑟 山东人学硕士学位论文 12 312 312 3123 2123 2 五= 3 州 2132 3 厄= 3 由上述标号可见， 行染色。 可 对于氖= 4 的 州 21231 磊= 3 州 13 213 2 州 21321 磊= 3 12 3121 州 21 3232123 2 磊= 3磊= 3 有2 种情况磊= 4 ，其他都是磊= 3 ：即均可由3 种颜色进 132 2 41 磊= 4 以加一个剖分点，可以得到以下结论。 加法 12 和 有如下情况： 2 2 41 2 4 1 w 2 2 4 3 2 不= 4 23 2 2 种情况，我们 ，故剖分点的 132132 13 231 w 2 41 w 2 2 4 1 2 2 4 1 2 1 9 山东大学硕士学位论文 我们可以重新进行进行标号，有以下结果： 231 2 31 w 132 132 121 3 1 ww 2 3 1 2 2 32 2 2 1 3 2 可以得到加一个剖分点可以用3 种颜色进行染色，即厄= 3 有如下情况： 2 0 结构的情况是 23 13121 2 31 24 32312 131 212 31 2 4 323 12 131212 31 ，故剖分点的加 24 32312 2 4 323 1224 32312 山东大学硕士学位论文 我们可以重新进行进行标号，有以下结果： 132132 31 2132 11 2 121 321 3 1 2323212 2321 32 221 32 132 可以得到加一个剖分点可以用3 种颜色进行染色，即五= 3 综上所述，( 1 ) 两条路不加剖分点时，有2 种情况矶= 4 ，其他情况都是矶= 3 ： ( 2 ) 两条路加1 个剖分点时，有疋= 3 。 2 4图g 中只有3 及以上条路的点色数 定理4 ：3 条路进行染色都可以用3 种颜色，即厄= 3 。 对于3 条路可以看成在2 条路中再加入1 条路。对于2 条路不加剖分点有2 种结果，我们也按照( 1 ) 磊= 3 ( 2 ) 矶= 4 进行讨论 ( 1 ) 对于2 条路中磊= 3 情况，2 条路的始边和终边端点相邻的标号一定互 2 l 山东大学硕士学位论文 不相同，所有有以下几种情况： 对于第3 条路的结构有 2 3 3 2 乙砬一 对于情况，由2 条路结果可知，插入第3 条路的6 种结构均可由3 种 颜色进行染色；而对于情况，若两条路相邻的一端为，另一端为 ，则可对另一端进行染色即可，若两端均为，可以按照下列情况进行 讨论。 ( i ) 若两端同为或或，可以讨论其中一种情况，其他两种情 况类似。在2 条路中插入第3 条路出现情况有如下结构： 对于 12 1 2 12 121 2 12 123 12 w 2121 我们可以重新标号为 山东大学硕士学位论文 w 2121 1 2 13 2 w 2 321 重新标号后就出现了的某一情况，由2 条路结果可知，均可由3 种颜 色进行染色。 ( i i ) 若两端为情况有如下结构： 12 31 1213 v 213 1231 2131 对于警们可以重新标号为 对于 1213 n 21 31 1 3 2 1 v 我们可以重新标号为 213 1313 n 21 21 重新标号后就出现了的某一情况，由2 条路结果可知，均可由3 种颜 色进行染色。 ( i i i ) 若两端为情况有如下结构： 对于 1213 2 z 31 z j 州 213 2 32123 2 12132 叭 2132 3 我们可以重新标号为 吣 2 312 3 山东大学硕士学位论文 对于 123123 vn 21 232 我们可以重新标号为 12 13 23 2 3 212 重新标号后就出现了的某一情况，由2 条路结果可知，均可由3 种颜 色进行染色。 ， ( i v ) 若两端为情况有如下结构： 对于 对于 1 3 123 吣州 31232 31323 13123 ln 3 123 2 132132 州 我们可以重新标号为 我们可以重新标号为 31323 重新标号后就出现了的某一情况， 色进行染色。 1 3213 吣 321 3 2 13 1 2 32 3 2 313 由2 条路结果可知，均可由3 种颜 所以对于2 条路中磊= 3 情况，插入第3 条路也有磊= 3 ( 2 ) 对于2 条路中以= 4n 况是 132 对于第一2 4 1 磊= 4 32 我们可以把左半部分 和 4 1 243 2 氛= 4 染成 12 2 种情况， 3 1 山东大学硕十学位论文 这样就相当于在 颜 色进行染色。 对于第二种情况， 2 3 我们可以把左半部分 这样就相当于在 由3 插入一条路，由2 条路结果可知，均可由3 种 3 121 w 432 1123 231 染成 12 31 w 312 插入一条路，由2 条路结果可知，均可 种颜色进行染色。 所以对于2 条路中磊= 4 情况，插入第3 条路也有厶= 3 。 综上所述，3 条路进行染色都可以用3 种颜色，即磊= 3 。 对于刀4 条路的情况可以仿照3 条路的情况进行讨论，也有舭= 3 的结果。 山东大学硕士学位论文 可 第三章最大度为2 ，3 和5 的双外平面图的点染色 1 当= 2 时，由引理2 可知，磊= 2 。 2 当= 3 时，由引理1 可知，舭= 3 。 3 a = 5 时，5 度点结构 ?l 中间的边不能再动，两边的端点 再连边，所以5 度点可能与2 个3 度点，1 个3 度点和1 个4 度点，2 个4 度点， 1 个4 度点和1 个5 度点，2 个5 度点，情况如下： 而 2 6 2 个3 度点 7 232 1 个3 度点和1 个4 度j 2 个4 度点 用3 种颜色可染且结构可变为 1 3 7 n 23 2 3 1 3 n 23 2 ? 可化为 用3 种颜色可染且结构可变为 用3 种颜色可染且结构可变为 山东大学硕士学位论文 变为 1 个4 度点和1 个5 度点 3 1 3 1 渺 23 2 用3 种颜色可染且结构可 出现了1 个6 度点，此6 度点 用3 种颜色可染且结构可变为 2 个5 度点 1 3 131 。 炒沌 23 2 最终所有5 度点均可化为 3131 沙 2 用3 种颜色可染且结构可变为 和 这样就可以转化到第二章所讨论的所有情况。 两种结构且a = 4 2 7 山东大学硕士学位论文 参考文献 1 j a ，默帝u s r 图论及其应用 m 吴望名等译北京：科学出版社，1 9 8 4 2 孔立一个特殊双外平面图的全染色 j 洛阳大学学报2 0 0 5 ( 6 ) 3 陈东灵，吴建良外平面图的一个结构定理 j 山东科技大学学报1 9 9 9 ( 4 ) 4 b o r o d i n g0v o nt h et o u t a lc o l o r i n go fp l a n n a rjr e i n e a n g e wm a t h 1 9 8 9 ， 3 9 4 ： 5 王光辉外平面图的围长和分数色数 j 山东大学学报( 理学版) 2 0 0 3 ( 1 2 ) 6 张苏梅外平面图的边面列表染色 j 山东农业大学学报1 9 9 8 ( 3 ) 7 陈明关于平面图全染色的一个注记 j 浙江师范大学学报2 0 0 7 ( 4 ) 8 张苏梅高度平面图的l ( p ，q ) 一标号 j 山东大学学报( 理学版) 2 0 0 7 ( 4 ) 9 孙向勇特殊平面图的全染色 j 山东师范大学学报( 自然科学版) 2 0 0 7 ( 1 ) 1 0 吴建良系列平行图的列表边染色 j 山东大学学报( 自然科学版) 2 0 0 0 1i 史天治平面图与对偶原理 j 长春师范学院学报2 0 0 6 ( 1 0 ) 1 2 张苏梅外平面图的l ( d ，1 ) 一标号 j 济南大学学报( 自然科学版) 2 0 0 6 ( 3 ) 1 3 孔立双外平面图的全染色 j 山东轻工业学院学报2 0 0 5 ( 2 ) 1 4 孔立双外平面图的边面染色 j 烟台师范学院学报( 自然科学版) 2