（运筹学与控制论专业论文）平方图的点荫度(1).pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：垃日 驾7 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：蝉导师签名：盟日期：生卑 山东大学硕士学位论文 平方图的点荫度 马刚 ( 山东大学数学与系统科学学院，济南，2 5 0 1 0 0 ) 中文摘要 本文中考虑的图都是简单图分别用v ( g ) ，e ( g ) 。i g i ，a ( g ) ，6 ( c ) 表 示图g 的点集合，边集合，点的个数，最大度和最小度对z v ( a ) ，用 r g 扛) 表示在g 中与点z 相邻的所有点的集合，用d g ( z ) 表示点z 的度度为k 的点称 为k 一度点 设g 是个图，g 的个一着色f 是从v ( a ) 到1 2 ，的个映射对 于图g 的给定的一着色，k 表示g 中所有染i 色的顶点集( 1 i s ) ，( k ) 表 示g 中由磁导出的子图若对于任意的i ( 1 i ) ，都有似) 是森林，则称，是 一个一树着色使g 有一树着色的最小数k 称为图g 的点荫度，记为n ( g ) ， 若对于任意的i ( 1 t ) ，都有( k ) 的每个连通分支都是路，则称，是个k 一 路着色使得图g 有一路着色的最小正整数称为图g 的点线性荫度，记为 v l a ( g ) ，显然v a ( g ) v i a ( g ) x ( g ) 任意两点u ，口矿( g ) ，它们之间的距离为连接这两个点的最短路的长度， 用d i s t a ( u ，口) 表示图g 的平方图g 2 是以v ( g ) 作为它的点集，两个点“，口 在g 2 中相邻当且仅当1sd i s t a ( u ， ) 2 ， 对于平面图，显然有下面著名的四色定理 定理1 1 3 2 1 3 3 1 1 3 4 】若图g 是平面图，则x c g ) 4 对于平面图的平方图的点着色，w e g n e r 3 5 】在1 9 7 7 年提出了如下猜想； 猜想2 3 5 】若图g 是平面图，它的最大度为a ，则 彬，汛辩。， 姜篙 7 【2 l 】 2 2 】 2 3 】【2 4 】中部分的证明了这个猜想 山东大学硕士学位论文 本文中我们主要考虑平方图的点荫度和点线性荫度本论文的第一节主要介绍 了平方图及点荫度和点线性荫度的基本概念和一些背景知识，第二，三，四，五节 依次讨论了树图。外平面图， 4m i n o rf r e e 图，平面图的平方图的点荫度和点线 性荫度，第六节讨论了两个完全图的笛卡儿乘积图的点荫度和点线性荫度本文的 主要结果如下； lt 是一棵树。它的最大度为，那么 v a ( t 2 ) = f 学 ， 丁l x + 1 1 v l a ( t 2 ) 会 + 1 2 g 是一个外平面图，它的最大度a 6 ，则 口o ( g 2 ) = 垒爿 3 图g 为局i l l , l o t f r e e 图，它的最大度为，则 叫哪 ，筝+ 。l ，瓮? 4 图g 是一个平面图，它的最大度为。那么 v a ( g 2 ) a + 1 3 5 当m = n = 2 k ( k z + ) 时，伽 ( x ) = v i a ( k mx ) = k + 1 ； 其它情况下。v a ( k 。) = 口f ( 七。k ) = m o z 愕i n l ，号1 关键词t 点荫度，点线性荫度，平方图，树，外平面图。段m i n o rf r e e 图，平 面图。乘积图 2 山东大学硕士学位论文 v e r t e xa r b o r i c i t yo fs q u a r eg r a p h s m ag a n g ( s c h o o lo fm a t h e m a t i c sa n ds y s t e ms c i e n c e ，s h a n d o n gu n i v e r s i t y , j i n a n2 5 0 1 0 0 ) a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t e ，l o o l c s s ，a n dw i t h o u tm u l t i p l e e d g e s f o rag r a p hg ，l e ty ( g ) ，e ( g ) ，f g l ，( g ) ，a n de ( a ) d e n o t e ，r e s p e c t i v e l y , i t sv e r t e xs e t ，e d g es e t ，n u m b e ro fv e r t i c e s ，m a x i m u md e g r e e ，a n dm i n i m u md e g r e e f o rz y ( g ) ，l e tn g ( x ) d e n o t et h es e to fn e i g h b o r so fzi nga n dl e td a ( z ) d e n o t e t h ed e g r e e ，i e ，t h en u m b e ro fn e i g h b o r so f i ng av e r t e xo fd e g r e eki sc a l l e da k - v e r t e x l e tgb eag r a p h ak v e r t e xc o l o r i n gfo fgi sa i li n j e c t i o nf r o mv ( g ) t o 1 ，2 ，k ，i ft h e r ei sak - v e r t e xc o l o r i n go fg ，l e tkd e n o t et h ev e r t i c e so fg w i t h c o l o ri ( 1 i ) ，( k ) d e n o t et h es u b g r a p ho fgi n d u c e db y w ec a l lfak - t r e e c o l o r i n gi f ( k ) i sat r e ef o re v e r yi ( 1 ) t h ev e r t e xa r b o r i c i t yo fg ，d e n o t e d b yv a ( g ) i st h es m a l l e s tn u m b e rkf o rw h i c ht h e r eh a sa 一t r e ec o l o r i n go fg w e c a l lfak - p a t hc o l o r i n gi fe v e r yc o m p o n e n to f ( k ) i sap a t hf o re v e r yi ( 1 i ) t h ev e r t e xl i n e a ra r b o r i c i t yo fg ，d e n o t e db yv l a ( a ) ，i st h es m a l l e s tn u m b e rkf o r w h i c ht h e r eh a sak - p a t hc o l o r i n go fg i ti so b v i o u st h a tv a ( g ) v l a ( g ) sx ( g ) l e tu ， i st w ov e r t i c e so fg ，t h ed i s t a n c eb e t w e e nua n dv ，d e n o t e db yd i s t ( u ，v ) i st h el e n g t ho ft h es m a i l e s tp a t hb e t w e e n “a n dv t h es q u a r eg r a p hg 2o fag r a p h gi st h eg r a p hd e f i n e dd nt h ev e r t e xs e t v ( g ) s u c ht h a tt w ov e r t i c e sua n d va r e a d j a e e n ti ng 2i f a n do n l yi f1 d i s t a ( u ，v ) s2 f o rp l a n a rg r a p h ，w eh a v e t h e o r e m1 【3 2 1 3 3 1 1 3 4 i fgi sap l a n a rg r a p h ，t h e nx ( g ) 4 f o rt h es q u a r eg r a p ho fp l a n a rg r a p h ，w e g n e r 【3 5 1i n1 9 7 7c o n j e c t u r e dt h e f o l l o w i n g 3 山东大学硕士学位论文 c o n j u c t u r e2 3 5 】l e tg b eap l a n a rg r a p hw i t hm a x i m u m d e g r e ea ，t h e n ) 【糊a + + 5 。 i f4 8 【2 1 2 2 1 1 2 3 2 4 h a v ep a r t i a l l yp r o v e dt h i sc o n j e c t u r e i nt h i sp a p e rw em a i n l yd i s c u s st h ev e r t e xa r b o r i c i t ya n dv e r t e xl i n e a ra r b o r i c - i t yo fs q u a r eg r a p h i nt h ef i r s ts e c t i o no ft h i sp a p e r ，w ei n t r o d u c es o m ed e f i n i t i o n s a b o u ts q u a r eg r a p l i s ，v e r t e xa r b o r i c i t ya n dv e r t e xl i n e a ra r b o r i c i t y ；i nt h es e c o n d ， t h et h i r d ，t h ef o u r t ha n dt h ef i f t hs e c t i o n s ，w ed i s c u s sq u e s t i o n so ft h ev e r t e xa r - b o r i c i t ya n dv e r t e xl i n e a ra r b o r i c i t yo fs q u a r eg r a p h so ft r e e ，o u t e r p l a n a rg r a p h ， k 4n l i n o rf r e eg r a p ha n dp l a n a rg r a p h ；i nt h el a s ts e c t i o no ft h i sp a p e rw ed i s c n s s t h ep r o b l e mo ft h ev e r t e xa r b o r i c i t ya n dv e r t e xl i n e a ra r b o r i c i t yo ft h ec a r t e s i a n p r o d u c to ft w oc o m p l e t eg r a p h t h em a i nr e s u l t so ft h i sp a p e ri sf o l l o w s 1 i ft i sat r e ew i t hm a x i m u md e g r e e t h e n v a ( t 2 ) = f 下a + i ， f 丁a + i v l a ( t 2 ) s 会1 + l | 2 i fgi sa no u t e r p l a n a rg r a p hw i t hm a x i m u md e g r e e 26 ，t h e n v a ( g d = f 垒期 3 i fgi sa 虬m i n o rf r e eg r a p hw i t hm a x i m u md e g r e ea ，t h e n 州哪 ，筝+ 。1 0 翟 4 i fgi sap l a n a rg r a p hw i t hm a x i m u md e g r e ea t h e n v a ( g 2 ) + 1 3 5 i f m = n = 2 k ( k z + ) ，t h e nv a ( 。k ) = v l a ( 版。k ) = + 1 ； e l s e ，v a ( k 。k ) = z 口( 丘。k ) = m 罟1 ，哮n 1 ) k e yw o r d s ：v e r t e xa r b o r i c i t y , v e r t e xl i n e a ra r b o r i c i t y , s q u a r eg r a p h ，t r e e ， o u t e r p l a n a rg r a p h ，虬m i n o rf r e eg r a p h ，p l a n a rg r a p h ，p r o d u c tg r a p h 4 山东大学硕士学位论文 第一节综述 图论是一门应用十分广泛其内容又十分丰富的数学分支，是近几年来比较活跃 的数学分支之一它起源很早，瑞士数学家欧拉( l e u l e r ) 在1 9 7 6 年解决了当时非 常有名的一个数学难题。即哥尼斯城堡七桥问题，从而使得他成为图论这门学科的 创始人2 0 世纪后，图论的应用渗透到许多其他学科领域如物理，化学。信息学， 运筹学，博弈论，计算机网络，社会学，语言学，以及集合论，矩阵论等从2 0 世纪 5 0 年代以后，计算机的迅速发展，有力的推动了图论的发展，使图论成为数学领域 中发展最快的分支之一 本章中我们首先介绍了图论的基本概念及一些重要的结果，最后我们证明了关 于平方图的点荫度的一个般结果 一个图g 是指个有序三元组( y ( g ) ，e ( g ) ，妒g ) ，其中v ( a ) 是非空的顶点 集，e ( g ) 是边的集合，而惦是关联函数，它使得g 中每一条边对应于g 的无 序顶点对( 两顶点可以相同) 若在图g 中。e 是一条边，札，口是两个顶点，满足此( e ) = 删。则称e 连接 u 和 ，点“和点”称为边e 的端点，也称u 和u 相邻，同时也称“( 或 ) 与e 关 联同一个顶点关联的若干条边称为是相邻的两个端点重合为一个顶点的边称为 环。关联于同一对顶点的二条或二条以上的边称为多重边一个图g 若没有环和 多重边，则称该图为简单图 如果一个图g 的顶点集v ( a ) 和边集e ( c ) 都是有限集，则称该图为有限图 否则称为无限图 通常我们将图g = ( y ( g ) e ( g ) ，妒g ) 简记为g = ( 矿( g ) ，e ( g ) ) 或g = ( 矿e ) 或g 。图g 的顶点数和边数分别用v ( v ) 和e ( g ) 表示。般在不至于混淆的情况 下用y ，e 。u ，来表示图的顶点集，边集，顶点数和边数 图g 中，与顶点 相关联的边数( 每个环计算两次) 称为点 的度，记为d ( v ) 分别用d ( g ) 和( g ) 表示g 中顶点的最小度和最大度度为零的顶点称为孤立 点度为1 的点称为悬挂点，与悬挂点相关联的边称为悬挂边 如果对所有 v ( c ) ，有d ( v ) = 膏，则称图g 是k 一正则的例如，。是 n 一正则图。 顶点“的所有邻点的集合称为“的邻域，记为 b ( ) g = ( ve ) 和5 1 = ( v 7 ，e ) 是两个图，若y 和e ，则称日是g 的子图，记为日g 如果日是g 的子图，并且y ( h ) = v ( a ) ，则称日是g 的生成子图 5 山东大学硕士学位论文 图g 的个点边交错出现的有限序列w = r o e l 啦e 2 2 仇一1 e k v k ，这里v d o isk ) 是g 的顶点，白( 1 i k ) 是g 的边，满足岛的两个端点就是u l 和 饥，则称是g 的一条从蛳到仇的途径，简称为( y o ，v k ) 一途径如果途径的 边不重复，则称这条途径为迹如果一条途径的顶点不重复，则称这条途径为路 如果一条途径的起点和终点相同，则称这条途径为闭途径把起点和中间点互 不相同的闭迹称为圈 连通的无圈图称为树对树显然有下面两个结论t 命题l 1 2 7 】若g 是一棵树，则= p 一1 命题1 2 1 2 7 1 一个连通图是一棵树当且仅当它的每一条边都是割边 如果一个图能画在平面上使得它的边仅在端点相交，则称这个图为平面图平 面图g 的边把整个平面分割成若干个连通区域。这些区域的闭包称为平面图g 的 面；外部的无限区域称为外部面我们分别用f ( g ) 和咖( g ) 表示平面图g 的面的 集合和面的个数对于平面图，显然有下面结论 命题1 3 1 2 7 图g 是一个平面图， 是它的一个点，那么存在g 的一个平面 嵌入使得点 出现在这个平面嵌入的外部面上 命题1 4 ( 欧拉公式) 若图g 为连通的平面图，则一+ 妒= 2 染色问题是图论中具有重要理论意义和现实意义的图论问题，它起源于一百多 年前的四色问题所谓四色猜想是在平面上的任何一张地图上，总可以用至多四种 颜色给每一个国家染色，使得任何相邻国家的颜色都不相同四色问题是图论中最 困难的问题之一，直到1 9 7 6 年才被美国的a p p e l 和h a k e n 借助高速计算机证明四 色猜想成立下面我们依次来看一下边染色，点染色以及点荫度和点线性荫度的概 念 对图g ，给它的边染色使得相邻的边染不同的颜色，则称这个染色为正常边 染色使得g 有正常边染色的最少颜色数称为g 的边色数，用x ，( g ) 表示对于 边染色，v i z i n g ( 1 9 6 4 ) 和g u p t a ( 1 9 6 6 ) 各自独立的得出如下重要结论； 命题1 5 1 2 8 1 1 2 9 】( v i z i n g 定理) 对于任何简单图g ，有( g ) = a 或x ，( g ) = + 1 根据v i z i n g 定理，若图g 满足x ，( g ) = a ，则称g 为第一类图；若图g 满 足x ，( g ) = a + 1 ，则称g 为第二类图确定图的分类问题是图论中一个非常困难 的问题，至今仍然没有完全解决 对图g ，给它的点染色使得相邻的点染不同的颜色，则称则称这种染色为正 常点染色使得g 有正常点染色的最少颜色数称为g 的点色数，用x ( c ) 表示与 6 山东大学硕士学位论文 点染色相关的最有名的问题当属四色问题，这个问题已经被解决- 命题1 6 1 3 2 3 3 1 1 3 4 】若图g 是平面图，有x ( c ) 4 类似于边染色中的v i z i n g 定理，b r o o k s ( 1 9 4 1 ) 证明了如下结论 命题1 7 2 0 若图g 是连通的简单图，且它不是奇圈也不是完全图。则有x ( g ) s 对图g 的顶点进行染色，使得染每一种颜色的点的导出子图为森林，则称这 种染色为树着色使g 有树着色的最小颜色数称为闭g 的点荫度，记为口n ( g ) 对图g 的顶点进行染色，使得染每一种颜色的点的导出子图为不想交的路，则称 这种染色为路着色使得图g 有路着色的最小正整数称为图g 的点线性荫度，记 为v i a ( g ) 显然v a ( g ) v l a ( g ) sx ( g ) 对于一般图的点荫度，k r o n k 和m i t c h e m 于1 9 7 5 年得到下面的结论t 命题1 8 1 1 2 1 若图g 是连通的简单图，且它不是圈也不是含有偶数个点的完全 图，贝4 有v a ( c ) sf - - 笋1 m a t s u m o t o 于1 9 9 0 年把上面的结果推广到点线性荫度上面，得到如下结论， 命题1 9 1 4 若图g 是连通图，则 ( 1 ) 图g 存在( 1 + i 垒盟2j i ；、一着色使得它的染每一种颜色的点的导出子图的每 个连通分支或者为矾或者为鲍； ( 2 ) v l a ( g ) 1 + 【掣j ； ( 3 ) 若( g ) = 2 n ，则v l a ( g ) = 1 + l 垒皿2j 当且仅当g 是个圈或者l + 1 m i c h e m 于1 9 7 0 年考虑了一个图的点荫度和它的补图的点荫度之间的关系得 到如下结论t 命题1 1 0 1 1 5 】g 是一个图，它有p 个点，则 妇v a ( c ) + f ( _ ) 1 + e + 2 l ； ：v a ( g ) v a ( - g ) 【字】2 ； 上面不等式中所有的界都是严格的 a l a v i 等人推广了上面的结果。分别于1 9 9 1 年和1 9 9 4 年得到如下结论 命题1 1 1 2 】g 是一个图。它有p 个点。则 伽v i a ( g ) + 口k ( 召) 1 + 警； ：v l a ( g ) v l a 回) s ( 盈铲1 2 ； 上面不等式中所有的下界除去p = ( 2 n + 1 ) 2 的情况下都是严格的。 7 山东大学硕士学位论文 命题1 1 2 1 4 g 是一个图，它有p 个点，则 u f o ( g ) + v l a ( - g ) 1 4 - f 警1 ； v l a ( g ) v l a ( 召) 【( ( p + 3 ) 2 2 ) 2 j ； 当p = ( 2 n + 1 ) 2 ( n z + ) 时，有2 n 4 - 2 sv l a ( g ) 4 - v t a ( - d ) 任意两点u ， y ( g ) ，它们之间的距离为连接这两个点的最短路的长度， 用d i s t a ( u ，v ) 表示图g 的平方图g 2 是以v ( a ) 作为它的点集，两个点u ， 在g 2 中相邻当且仅当1 d i s t a ( u ，t ，) 2 但是，平方图的点荫度和点线性荫度还没有引起人们的重视本文中我们主要 考虑平方图的点荫度和点线性荫度对任意图g 显然有如下结论； 定理1 1 3 图g 为简单图，它的最大度为，则垒笋1 v a ( 6 a ) 下2 t 2 - b 1 1 证明，设g 中存在点u 使得d g ( 口) = ，那么点 及与点u 相邻的点在g 2 中构 成一个点数为+ 1 的完全图k “1 ，而u o ( 如+ 1 ) = x f + 1 1 ，从而v a ( t 2 ) f - i - - 下面证明v a ( g 2 ) f 垒 ，对l g i 用数学归纳法 当i g i = 4 - l 时。此时( 产为完全图+ l 。结论显然成立 当g i = n ( n + 1 ) 时，我们假设结论对点数小于n 的任意图成立由 于g 的最大度为。所以( g 2 ) 2 ，从而可以在图g 中找到一点口满足 啦( ) a 2 。令h = g 一口，则i 何i i g l ，从而v a ( h 2 ) 垒1 由于 d 6 n ( v ) 2 2 垒1 ，日2 的一个a 2 广+ i 一树着色容易扩充到( 产上，从而 v a ( g 2 ) 垒1 ，结论成立 口 定理1 中的上界是可以达到的，对5 _ 圈g 和p e t e r s e n 图，显然有v a ( 6 。) = v l a ( g 2 ) = 垒；竽1 8 山东大学硕士学位论文 第二节树的平方图的点荫度和点线性荫度 本章中，我们主要考虑树的平方图。并得到关于树的平方图的点荫度和树的平 方图的点线性荫度的两个结果文章最后，我们给出例子以说明我们的结果是最好 的对树丁，点l ，v ( t ) ，当如( ) = 1 时，我们称”为叶节点( 悬挂点) 定理2 1t 是一棵树，它的最大度为，那么v a ( t 2 ) = a r + i 证明：由定理1 1 3 ，我们只需证明v a ( t 2 ) 掣 ，对t 中非叶结点的个数用 归纳法证明 当丁中有0 个非叶结点时，此时t 为一条边，显然有口n ( p ) = 1 = f 垒# 当丁中有1 个非叶结点时，此时t 为星型图，p 为点数为+ 1 的完全 图如+ 1 ，显然有v a ( t 2 ) = t x r + l - 当t 中有k ( k 2 ) 个非叶结点时。我们假设对非叶结点个数小于k 的树结 论成立由于t 是一棵树，故必然存在一个非叶结点z y ( t ) ，使得它只与另 外一个非叶结点相邻记与z 相邻的那个非叶结点为y ，与z 相邻的那些叶结点 为z ，z z ，( t ) 树t 中除去与z 相邻的叶结点后得到一颗新树乃，显 然丑中至多有k 一1 个非叶结点。由归纳假设知 o ( 砰) l x 百+ 一i 给图砰一 个垒笋1 一树着色，下面把这种着色扩充到p 上，即给点z 。，0 2 ，进行染色 我们用学1 种颜色对z i ，x 2 ，x t 进行任意染色满足在点z ，y ，i x 2 ，觑中 至多有两个点染同一种颜色，由于t ，所以t + 2 + 1 ，所以这种染色是容 易做到的这样我们得到了图铲的个垒芋1 一树着色，从而有v a ( t 2 ) f a r + 1 1 ， 命题得证 口 定理2 2t 是一棵树，它的最大度为，那么j x f + 1 v a ( t 2 ) 吟1 + 1 证明：由定理1 1 3 ，我们只需证明v l a ( t 2 ) sf 钔+ 1 ，对t 中非叶结点的个数 用归纳法证明 当t 中有0 个非叶结点时，此时t 为一条边，显然有v l a ( t 2 ) = 1 2 = 钔+ 1 当t 中有1 个非叶结点时，此时r 为星型图，铲为点数为+ l 的完全 图如+ 1 ，显然有v l a ( t 2 ) = 下a + i 铜+ 1 当r 中有k ( k 2 ) 个非叶结点时。我们假设对非叶结点个数小于k 的树结 论成立由于丁是一棵树，故必然存在一个非叶结点z 矿( t ) 使得它只与另 外个非叶结点相邻记与z 相邻的那个非叶结点为，与。相邻的那些叶结点 9 山东大学硕士学位论文 为$ l ，z 2 ，z t ( t ) 树丁中除去与z 相邻的叶结点后得到一颗新树n ，显 然孔中至多有一1 个非叶结点。由归纳假设知v i a ( 砰) r 令1 + 1 给图砰一 个令1 + i - - 路着色，下面把这种着色扩充到t 2 上。即给点z l ，z 2 ，以进行染 色在刽+ 1 种颜色中除去点所染的颜色，用剩下的f 令1 种颜色对z 1 ，z 2 ，貌 任意染色满足在点x y ，x l ，z 2 ，至多两个点染同一种颜色由于t a ，这种 染色是容易做到的由于点x l ，x 2 ，x t 中每个点染的颜色都与点所染的颜色 不同，于是我们得到了? 2 得个f 铜+ 1 一路着色，从而v l a ( t 2 ) 除1 + 1 ，命题 得证口 注意到，定理2 2 中，当为偶数时，v i a ( 7 a ) 的上下界是相等的；当为奇 数时，v l a ( t 2 ) 的上下界相差为1 ，且上下界都是可以取到的显然，v l a ( k 1 2 ) = f t a + i ；下面我们对任意奇数a ，给出图丁，使得( 丁) = a ，r v l a ( t 2 ) = r 舍l + 1 我们从k 1 ，构造丁，给尥的每个叶节点连以a 一1 条悬挂点显然有 ( t ) = 。且v l a ( t 2 ) = 除 + 1 下面给出路色数的定义- 对图g 的顶点进行着色，使得着每一种颜色的点 的导出子图的每个分支为长度不大于k 的路，满足这个条件所需的最少颜色数称为 k - 路色数，记为x ( g ，最) 定理2 3t 是一棵树，它的最大度为a ，那么产a r + i s x ( 铲，b ) s 学1 + 1 证明：设g 中存在点 使得d g ( ”) = a ，那么点 及与点t ，相邻的点在g 2 中构成一个点数为+ 1 的完全图如+ l ，而显然有x ( j 厶+ 1 p 2 ) = 下a + 1 1 ，从 而x ( 俨，岛) a r + 1 1 下面证明x ( 铲，p 2 ) 下a + i + 1 ，对t 中非叶结点的个数用归纳法证明 当丁中有0 个非叶结点时，此时t 为一条边，显然有x ( t 2 ，p 2 ) = 1 2 = 垒笋 + 1 当丁中有1 个非叶结点时，此时r 为星型图，7 ”为点数为+ 1 的完全 图如+ 1 ，显然有x ( p ，p 2 ) = 丁l 、- r i 垒笋1 + 1 当t 中有k ( k 2 ) 个非叶结点时，我们假设对非叶结点个数小于k 的树结 论成立由于r 是一棵树，故必然存在一个非叶结点z y ( 丁) ，使得它只与另 外一个非叶结点相邻记与z 相邻的那个非叶结点为y ，与z 相邻的那些叶结点 为x l ，x 2 ，轨( t ) 树丁中除去与z 相邻的叶结点后得到一颗新树乃，显 然n 中至多有一1 个非叶结点，由归纳假设知x ( 俨，p 2 ) 掣1 十1 给图砰一 个竿1 + 1 - 着色，使得每种颜色的导出子图的每个分支为长度不大于2 的路 下面把这种着色扩充到俨上，即给点z t ，z z ，z t 进行染色在掣1 + 1 种颜 色中除去点，所染的颜色，用剩下的掣 种颜色对z l ，z 2 ，轧任意染色满 1 0 山东大学硕士学位论文 足在点z ，”，z l ，z 2 ，t 至多两个点染同一种颜色由于t + 1 ) 个点，假设对点数小于n 的2 一连通的外平面图结论成 立由引理3 2 知，g 中存在- - + 2 一度点1 使得如。似) sm a x 7 ， 2 r a + 1 1 若包含“的面为一个3 一面。令h = g 一让，此时有g 2 一u = h 2 若包含t t 的 面为一个4 面，且与 相邻的两个点分别为z 。y ，令h = g 一“+ x y ，此 时g 2 一札sh 2 ，则l y ( 日) i i 矿( g ) l ，由归纳假设，v a ( h 2 ) f 垒岩 给定h 2 的 个垒笋1 一树着色，由于d a ，( u ) 2 竽1 ，必存在一种颜色或者没有在 r g ：( “) 中出现过或者在n m ( u ) 中只出现过一次，给点 i t 染这种颜色，我们得到了g 2 的 个户a r + 1 1 一树着色，从而v a ( c 2 ) 丁a + i ，命题得证 口 定理3 4 g 是个外平面图，它的最大度a 6 ，则v a ( g 2 ) = 垒笋 证明不失一般性，假设g 是连通图只须证v a ( c 2 ) t a + i 若g 中存在一个1 一度点z 1 ，令g t = g z 1 ；若g l 中仍然存在l 一度 点沈，令g 2 = g 1 一勋；这个过程重复进行，直到某个图g 中不再存在1 一度 点，此时显然有6 ( g k ) 2 记g 中被删除掉的点依次为z t ，勋，z k 山东大学硕士学位论文 我们首先证明对g k = h 有v a ( h 2 ) 垒z h r + 1 对h 中2 一连通块的个数用数 学归纳法 若日是2 一连通的，则由定理3 3 显然有v a ( h 2 ) 垒笋1 若日不是2 一连通的，设有q ( q 2 ) 个2 一连通的块，假设结论对块数小 于q 的不含l 一度点的外平面图成立h 中必存在一个块日1 使得它只与另外一 个块如通过一条路p 相连由引理3 2 及定理3 3 易知，v a ( h ) 垒1 若i ( p ) = 0 ，即h t 与仍有个公共点，设这个点为y ，在日中删去v ( h t ) 一 中所有点后得到的图记为霄，由归纳假设知u o ( 7 产) 垒# 。给定百2 的 一个垒笋卜树着色，由于v a ( h ) f 掣1 ，容易把这个染色扩充到日2 上，从 而v a ( h 2 ) 垒笋1 若l i p ) 1 ，设p = 1 1 1 v 2 咋( p 2 ) ，其中v l y ( 如) ，v ( h 1 ) 记 中删去v ( h 1 ) u v 2 ，一。 中所有点后得到的图为万。由归纳假设知 o ( 百2 ) 垒芳1 给定耳。的个垒1 一树着色依次给点耽( 2 i p ) 染色使得俨p d 中已染色的点中至多有两个点染同一种颜色由于u d ( 日 ) s 垒笋 ，容易把这种染 色扩充到整个日2 上，从而得到h 2 的个f 垒笋卜树着色，从而v a ( h 2 ) f 垒# 1 这样我们证明了v a ( h 2 ) f 垒笋1 给定h 2 的一个垒# 卜树着色，下面把 这种染色扩充到g 2 上t 依次给点x k ，钆“，1 染色使得n m z t l 已染色的点 中至多有两个点染同一种颜色这样我们得到了g 2 的一个垒# 一树着色，从 而v a ( g 2 ) s 垒笋1 ，命题得证 口 分别在= 3 ，4 ，5 时依次考虑引理3 2 中的各种情况。容易得到下面的结论 引理3 5 图g 是2 一连通的外平面图。它的最大度， ( 1 ) 若= 5 ，则存在2 一度点v ( g ) 满足d g 2 ( ) 6 ； ( 2 ) 若= 4 ，则存在2 一度点v ( g ) 满足d r ：( “) 6 ； ( 3 ) 若= 3 ，则存在2 一度点让v ( c ) 满足d c 。( “) 4 类似于定理3 4 的证明，并分别利用引理3 5 ，且考虑到= 2 时，外平面图 g 是路或圈，我们有如下几个结论t 1 4 定理3 6 图g 是一个外平面图，它的最大度为 ( 1 ) 若a = 4 或5 ，则3 v a ( g 2 ) 4 ； ( 2 ) 若= 2 或3 ，则2 su 口( g 2 ) 3 山东大学硕士学位论文 第四节k 4m i n o rf r e e 图的平方图的点荫度 若图g 可以通过收缩边得到图，则图h 称为图g 的m i n o r 若图g 不能 以日为m i n o r ，则称g 为h m i n o r f r e e 图本章我们考虑k 4 m i n o r f r e e 图的平 方图的点荫度图g 中，一口表示点“与点口在g 中相邻，即“ v ( v ) 定义 ( t ) = z l d g ( x ) 3 且t 一z ，或者存在个2 一度点。满足n 一。和。一z ) 。 令d g ( u ) = i ( “) i 立 引理4 1 1 2 2 】图g 为一个k 4m i n o rf r e e 图，则下面三个结论至少有一个成 ( 1 ) 6 ( g ) 1 ； ( 2 ) 存在两个相邻的2 一度点； ( 3 ) 存在点“满足d g ( “) 3 且d c ( u ) 2 定理4 2 囹g 为k 4 m i n o r f r e e 图，它的最大度为，则 州g 2 ，s 罔3 + 。鼍，繁 证明。当= 2 时，( g 2 ) 2 ( g ) 4 ，从而由定理1 1 3 知v a ( g 2 ) ， 垒翌2 丝1 半 - 3 下面假设3 ，我们对图g 的点的个数i g l 用数学归纳法为了叙述的方 便性。当= 3 时，令k ( a ) = 3 ；当4 时，令k ( x ) = 警1 + 1 当i g i 6 时，v a ( g 2 ) n ( k b ) = 3 ，命题成立下面假设i g i 7 且命题 对点数小于l g | 的任意k 4m i n o rf r e e 图日成立 若g 有一个1 一度点x ，令h = g z 显然日为一个t ：4 m i n o r f r e e 图， a ( h ) sa ( g ) 且g 2 一z 为日2 的一个子图，由归纳假设知v a ( h 2 ) k ( a ) 由 于d m ( x ) a ( g ) 2 k ( a ) ，从而g 2 一z 的一个k ( a ) - 树着色可以扩充到g 2 上。从而命题成立 若g 有两个相邻的2 一度点z ，设的另外一个邻点为z ，令= g z + y z 显然h 为个k 4 m i n o r f r e e 图，a ( h ) s a ( g ) 且g 2 一z 为h 2 的 个子图，由归纳假设知v a ( h 2 ) k ( a ) 由于d m ( x ) s a ( g ) + 2 2 k ( a ) ， 从而g 2 一$ 的一个k ( ) 一树着色可以扩充到g 2 上，从而命题成立 1 5 山东大学硕士学位论文 下面我们假设d ( g ) = 2 且不存在两个相邻的2 一度点根据引理4 1 ，g 中 存在一点满足d g ( 札) 3 和d a ( u ) 2 对t s 0 ( ) ，令m ( u ，t ) 为与点u ，t 相邻的2 一度点的集合，令m ( t ) = i m ( u ，) i 显然有d g ( u ) 1 若d g ( “) = 1 ，设( “) = z ，那么u 的邻点或者 为。或者为。的邻点。由于d g ( “) 23 ，所以m ( z ) 2 设w m ( u ，z ) ，令 h = g 一埘显然h 为一个虬m i n o r f r e e 图，z x ( h ) z x ( g ) 且g 2 一w 为2 的 个子图由归纳假设，v a ( h 2 ) k ( z x ) 由于如) a ( g ) + 1 2 k ( z x ) ， g 2 一z 的一个k ( ) 一树着色可以扩充到g 2 上。命题成立 当d c ( u ) = 2 时，令岛( “) = z ，计，点的所有邻点或者为刀，y 或者为z ，y 的邻点不失一般性，假设m ( x ) 2m ( u ) 由于如( n ) 3 ，所以m ( z ) 1 设 w m ( u ，z ) ，下面分三种情况证明 情况1z 一 令h = g 一 ，则h 为个心m i n o rf r e e 图，a ( h ) z x ( c ) 且俨一w 为 日2 的一个子图由归纳假设，v a ( h 2 ) k ( a ) 由于m ( x ) + m ( ) d g ( u ) 一2 ， r e ( x ) m ( ) ，我们有m ( z ) r 堑出2 二呈 i = g 学 一