（运筹学与控制论专业论文）图的群着色救.pdf

g r o u p n u m b e rc h r o m a t i c o f g r a p h s at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t s f o rt h em s d e g r e ei nm a t h e m a t i c s b y z h a n gj u a n p o s t g r a d u a t ep r o g r a m s c h o o lo fm a t h e m a t i c sa n ds t a t i s t i c s c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l ix i a n g w e n a c a d e m i ct i t l e ：p r o f e $ s o r s i g n a t u r e a p p r o v e d m a y 2 0 1 1 硕士学位论文 m a s t e r st h e s i $ 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：涨次舄日期：弘| 年岁月沙，日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：戤娟 日期z d f 年岁月艿日 导师签名： 砖撕父伽父 日期：o 1 年占月毯一日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库一中全文发布，并可按“章程中的 规定享受相关权益。回童迨塞握銮卮溢卮! 旦圭生；旦= 生；旦三生筮查! 作者签名：锹指 日期：p 年岁月殄日 导师戳：锄k 日期：初l | 年j 月扩日 硕士学位论文 m a s t e r st h e s i s 中文摘要 用g ；，) 表示一个图，a 代表一个非平凡的阿贝尔群，用f ( g ，彳) 表示所有 函数厂：e ( g ) 一彳组成的集合，用d 表示e ( g ) 的定向。我们说g 是a 一可着色的当 且仅当对于每一个厂e f ( g ，a ) 都存在着一个a 一着色c ：y ( g ) 呻a ，使得对每条边 e x ye e ( g ) ( 假设边的定向是由石发向y 的) ，c ( x ) - c ( y ) ( e ) 如果g 代表一个 图，我们定义它的群着色数九( g ) 是在定向d - f ，使得g 是彳一可着色的，i a l m 的 最小的i n 值。我们这篇论文主要涉及到的是群着色数和一些给出的结果。 令k m a x 日6 ( h ) ，其中h 是图g 的任一支撑子图，我们可以得出： x 譬( g ) s 七+ 1 简单图g 和日的笛卡尔乘积记作图g 口h ，这个图的顶点集合是 坎g ) 联日) ，它的边集是有所有的这些序列对 。，v o ( u ：，屹) 组成的，如果满足以 下两种情况：( 1 ) u l u 2e e ( g ) ，h 串t v , = ，2 ；( 2 ) v i v 2e e ( h ) ，同时u 1 = h 2 所以，我们 可以验证以( 只口己) = 3 ，以( 口c m ) - - 4 ，x 。( c 口巴) s 4 ，旃( q ) s 刀一1 本文主要证明的结论是：( 1 ) 令数a 3 ，图g 满足：a ( g ) sa ，并且k “旺g ， 那么有( g ) sa ；( 2 ) 对任意简单图g l 和g 2 有： ( g l 口g z ) s m a 】【仇( g 1 ) + 1 旎( g 2 ) + b 关键词：群着色数；最大度；连通图；笛卡尔积图；度序列；着色问题 一m a s t e r s t h e 淞 a b s t r a c t l e tg = ，) b eag r a p ha n dab ean o n - t r i v i a la b e l i a n g r o u p ，a n d l e t r ( a ，彳) d e n o t et h es e to fa l lf u n c t i o n s ，：e ( g ) 一a d e n o t eb yd a no r i e n t a t i o no f e ( g ) t h e ngi s a - c o l o r a b l ei fa n do n l yi ff o re v e r y 厂c v ( o ，彳) t h e r ee x i s t sa l l a - c o l o r i n gc ：y ( g ) 呻as u c ht h a tf o re v e r ye = x yee ( o ) ( a s s u m e dt ob ed i r e c t e d f r o mxt oy ) ，c ( x ) - c ( y ) ，p ) 1 fgi sa g r a p h ，w ed e f i n ei t sg r o u pc h r o m a t i cn u m b e r ( g ) t o b et h em i n i m u mn u m b e rmf o rw h i c hgi sa - c o l o r a b l ef o ra n ya b e l i a n g r o u pao fo r d e r mu n d e rt h eo r i e n t a t i o nd t h i sp a p e ri sm a i n l yc o n c e r n e dw i t h g r o u pc h r o m a t i cn u m b e ra n ds o m er e s u l t sa r eg i v e n g i v eag r a hgl e tk ；m a x 村6 ( h ) w h e r et h em a x i m u mi st a k e no v e ra l ls p a n n e d s u b g r a p h s ho f g ，t h e n 以( g ) s k + 1 t h ec a r t e s i a np r o d u c to fs i m p l eg r a p h s ga n dhi st h eg r a p hg 口hw h o s ev e r t e xi s 坎g ) 坎h ) a n dw h o s e e d g es e ti s t h es e ti fa l lp a i r s l ，y 1 ) 2 ，v 2 ) s u c ht h a t e i t h e r l ，u 2 ) ( g ) a n d 匕一v 2 ，o r h ，2 e e ( h ) a n d 比1m u 2 t h u s ，w ec a nc l e a r l yg e t s ，z g ( 只口己) = 3 ，z 暑( 只口c 。) s 4 ，以( c 口q ) - ：4 ，x , ( q n ) s n 一1 t h i sp a p e rp r i n c i p a l l yp r o v e st h a t , ( 1 ) l e t a 3a n dl e tgb eag r a p hs u c ht h a ta ( g ) saa n dk a + l 旺g ，t h e nz g ( g ) sa ； ( 2 ) l e tg 1a n dg 2b es i m p l eg r a p h s ，t h e n 以( g 1 口g 2 ) 5m a x z s ( g 1 ) + 1 , x s ( g 2 ) + 1 k e yw o r d s ：g r o u pc h o m a t i cn u m b e r ；m a x i m a ld e g r e e ；c o n n e c t e dg r a p h ；c a r t e s i a n p r o d u c t ；s e q u e n c e o fd e g r e e s ；g r a p hc o l o r i n gp r o b l e m 硕士学位论文 m a s t e r s t h e s i s 目录 中文摘要。一i a b s t r a c t 1 前言 1 1 学术背景和意义1 1 2 概念和符号说明1 1 3 图群着色相关问题的研究现状3 1 4 本文主要工作概述4 2 预备知识 6 2 1 补充概念6 2 2 已知结论6 3 主要结论 9 3 1 主要结论证明所需引理及其推论1 2 3 2 主要结论证明1 4 结束语 参考文献 致谢 1 8 1 9 2 1 硕士学位论文 m a s t e r st h e s i s 1 1 学术背景和意义 1 前言 一百多年前，英国格色里提出了用四种颜色即可对地图着色的猜想以后四色 猜想一直成为数学家感兴趣而未能解决的难题( 1 9 7 6 年美国数学家阿贝尔和黑肯宣 布，他们用电子计算机证明了四色猜想是成立的) ，现在我们将四色猜想可以叫做 四色定理了。就同数学中所有著名难题一样，四色问题得到解决的意义不单单就是 解决了一个数学上的悬案，更具有重大意义的是，在攻克这个壁垒的过程中，数 学家们发展了许许多多新的数学方法，开辟了许多新的研究方向，本文所要介绍 的就是图论中因四色问题而引起的一个研究专题图的着色问题。图着色问题在 组合分析和实际生活中有着广泛的应用背景，它不仅可以用于任务调度，资源分 配，排课表，v l s i 布线和测试等等问题上，而且还可以在目前大量科技，管理及 工业设计等领域上的大问题。 图的着色问题( g r a p hc o l o r i n gp r o b l e m ，g c p ) ，又称着色问题，是最著名的 n p 一完全问题之一。图着色问题起源于地图的着色问题：用m 种颜色为地图着色，使 得地图上每个区域着一种颜色，且相邻区域颜色不同。 通常所说的着色问题是指下述两类问题： 1 给定无环图g = ，e ) ，用m 种颜色为途中的每条边着色，要求每条边着一 种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。 2 给定无环图g 一，e ) ，用m 种颜色为图中的每个顶点着色，要求每个顶点 着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶点着色 问题。 本文主要研究顶点着色问题，并且将顶点着色扩充到阿贝尔群上，因此就得 到与一般顶点着色定理类似的结论。 1 2 概念和符号说明 在文中若无特殊说明，图g 就是简单的、有限的和无环的。对于边子集 x e ( c ) ，收缩子图g x 是图g 经过将石中所有的边上的两个顶点粘到一起作 硕士学住论文 m a s t e r st h e s i s 为一个新的顶点，并且删掉产生的环和平行边，而得到的一个新的图。 令图g = ，e ) ，a 表示一个非平凡的阿贝尔群，并且定义集合v ( o ，a ) ，它 是由全体函数f ：e ( g ) 一a 组成的。假设图g 的定向为d ，可以简记为d ( g ) ，则 用u v 表示d ( g ) 中的从h 发向v 的一条弧。 定义1 1 1 如果对于某一个函数厂e f ( v ，彳) ，存在另一个函数c ：y ( g ) 呻彳使得， 对于每一条有向边e = u v e e ( g ) 满足不等式c ( u ) 一c ( v ) f ( e ) ，那么我们就把函数 c 定义为图g 在定向d 下的似，) 一可着色的。 定义1 1 2 如果对于任意的厂，( g ，彳) 都存在一个似，厂) 一可着色的，那么我们 就说图g 在定向d 下是a 一可着色。 定义1 1 3 令图g 的定向是d ，如果对于任何阶数不少于m 的群a 来说，图g 都 是a 一可着色，那么我们就把满足上述条件m 的最小值定义为图g 的群着色数( t h e g r o u p c h r o m a t i c n u m b e r ) 。一般地，我们将图g 的群着色数记作以( g ) 本文符号说明 y ( g ) 图g 的顶点集合 e ( g ) 图g 的边集合 d ( g ) h y ( g ) 6 ( g ) v ( g ) v ( h ) g 口h r 只 图g 的定向d 从u 到v 的一条弧 图g 的最大度 图g 的最小度 图g 和图日顶点集合的笛卡尔积 图g 和日的笛卡尔乘积 树图 长度为n 的路 2 硕士学位论文 m a s t e r st h e s i s 顶点数为”的圈 1 3 图群着色相关问题的研究现状 先回顾一下图的一般着色，给定图g 的一个任意定向d ，如果图g 的每一个顶 点都可以被0 到七一1 中的任一个数标记，并且保证每一条边上的相邻顶点被标记的 数字不相等，我们说在定向d ( g ) 下，图g 是七可着色的。我们可以意识到，图g 是 k 可着色的，其实与在哪一个定向下是无关的。 与图最大度有关的一般着色数定理是众所周知的一个结果。 定理1 3 1 嘲对于任何连通图g ，以下结论都成立： z ( g ) sa + 1 ，其中表示图g 顶点的最大度。 定理1 3 2 p 令g 是一个连通图，如果g 既不是奇圈又不是完全图，那么 x ( a ) s 定理1 3 3 p 令g 是一个连通图，b 是图g 的块，那么有： z ( g ) = m a x x ( b ) ，b 是g 中的任何一个块) 定理1 3 4 p 1 令g 是一个连通图，它的补图假设为万，那么成立： z ( g 娩( 面以，其中以是图g 的阶数。 根据a 可着色的定义，我们首先应该明确图是否是群a 着色的，都与图g 的 任何定向无关。 定理1 3 5 p 对于任何图g 来说，都有： z ( g ) n 2 厶2 2 m ，其中万是图g 的阶数，小是图g 的边数 性质1 3 6 囝假设d 是( g ) 的一个定向，e o 是e ( g ) 的一个边子集。令d 是通过改 变晶在定向d 下的边上的方向得到的g 的一个新定向，a 表示一个非平凡的阿贝 尔群如果在定向d 下g 是a 可着色的，那么在定向d 下g 也是a 可着色的。 下面列举一些一般图群色数的基本知识。 定理1 3 7 嘲图g 的群着色数旎( g ) t2 当且仅当g 是森林。 3 硕士学位论文 m a s 丁e r st h e s i s 定理1 3 8 t z 对于任意的连通的简单图g 有 z g ( g ) s ( g ) + 1 ， 等号成立的充分必要条件为要么( g ) 一2 ，并且g 是偶图；要么a ( g ) 3 ，并且g 是完全图。 推论1 3 9 嘲任何图g 的群着色数满足 以( g ) sa ( g ) + 1 推论1 3 1 0 2 1 女h 果完全图g 的阶数为n ，那么图g 的群着色数满足 以( g ) = n 如果g 存在一个子图可以收缩为k ，那么我们就说一个图g 含有一个 k m i n o r 一个图g 是k m i n o rf r e e ，如果它不含任何的k m i n o r t 酗在【2 1 】，【2 2 和 【2 3 文中提到的库娃图斯基定理，我们可以得知简单平面图是不含有墨m i n o r 和 玛3 - m i n o r 的 定理1 3 1 1 4 如果图g 是简单平面图，那么 以( g ) s 6 定理1 3 1 2 伫2 l 2 3 1 如果g 是一个不含墨m i n o r 或是k 3 一m i n o r 的简单图，那么 1 4 本文主要工作概述 ( g ) s 5 本文主要研究了关于图的群着色的相关问题，并得到了一些与图的一般着色 相似结论。论文主要有以下安排： 在第二节里，根据图一般着色定理，经数的推广，得到图的群着色相关引理， 从而得出新的引理条件和类似引理结论。 在第三节中，首先举例子简要讨论了几个特殊简单图的笛卡尔 积图的群着色数，并且联想到笛卡尔积图的群着色数与构成它的两个简单图的群 着色数有着必然的关联，但是关于一般简单图的笛卡尔积图的群着色数还有待进 4 硕士学位论文 m a s t e r st h e s l 8 一步的研究；接着根据一般着色的结论，经过推广，将自然数扩充到阿贝尔群上， 得到了一系列基本的群着色定理及其推论；最后，列出本文主要结论，通过规定图 的一些性质，如图的最大度限制不超过，并且图中不含每个顶点度均为的 完全子图，我们就可以将图的群着色数缩小到不超过最大度；还得出：一般简单 图g 1g 2 的笛卡尔积图的群着色数以( g 1 口g ：) sm a x 仇( g 1 ) + 1 ，以( g 2 ) + q 5 硕士学位论文 m a s t e r st h e s i s 2 1 补充概念 2 预备知识 定义2 1 1 令图g 日g ，a 为一个非平凡的阿贝尔群。我们称( g ，胃) 是a 一 可扩展的，如果对于任意的f f ( g ，彳) ，以及任意的，l ( 日) 的a - 可着色的c ，都 存在g 的一个对于厂的彳- 可着色c 且c f y ( 日) = c 7 如果对于g 的任意子图h ，( g ，日) 都是a 可扩展的，g 是强a 可着色的。 定义2 1 2 简单图g 和h 的笛卡尔乘积记作图g 口日，这个图的顶点集合是 职g ) h h ) ，它的边集是有所有的这些序列对0 ，v o ( u ：，v ：) 组成的，如果满足以 下两种情况： ( 1 ) 1 ，“2 ) e ( g ) ，同时，l = ，2 ： ( 2 ) o l ， ，2 ) e ( 日) ，同时u 1 一u 2 2 2 已知结论 引理2 2 1 g 是森林，h g ，( g ，h ) 是z 2 可扩展的充分必要条件是日的 任意两个分支分属于图g 的不同分支。 引理2 2 2 已知图g 的顶点集合为v ( c ) - - - 鼍，x 2 ，) ，子图h g x l ，x ：，乇】， 假设h 是可一般着色的，顶点着色为1 ，2 ，3 ，k + 1 ，并且每一个石， + 1 s _ s 露 满足：如果它在h 中的邻点着了c j 种颜色，那么工，至多跟k c j 个顶点 毛， + 1s fs j ) 相邻，那么我们很容易得到 z ( g ) sk + 1 由引理2 2 2 ，假设h g ： ，不难得到下面一个定理。 6 嚣 硕士学位论文 m a s t e r st h e s i s 定理2 2 3 令图g 是一个简单图，d 化) = d i ，1s is n ，假设g = g 【化，k 小，k ) 】， 令g g 1 如果6 ( g ) sk ，那么 以( g ) s k + 1 在此定理成立的前提下，我们可以看有关几个简单的笛卡尔积图群着色数的结 论，这将在下节中介绍。 我们先看几个其它关于群着色的结论。 引理2 2 4 囱令彳是一个阿贝尔群，h g 如果( g ，日) 是彳可扩展的，而且日 是a 可着色的，那么g 也是a 一可着色的。 引理2 2 5 嘞令彳是一个阿贝尔群，h ：。g 如果( g ，h 1 ) 是彳可扩展的， 并且饵：，h 。) 也是彳一可扩展的，那么( g ，h 2 ) 也一定是彳- 可扩展的。 引理2 2 6 l l o g 是一个图，假设坎g ) 中所有顶点可线性排列为h ，屹，以，并且 满足d g 。“) k ( i = 1 ，2 ，刀) ，其中g = g 【 h ，v 2 ，u ) 】那么对于任意一个阶数不小于 k + 1 的阿贝尔群a ，( g 巾g ：f ) ( f = 1 ，2 ，刀) 是4 - 可扩展的，从而可知图g 是a 一可着色 的。 引理2 2 7 2 1 令g 是一个图， ，y ( g ) ，h = g 一 ，如果d g p ) 2 ，事实上，只口己不是森林，就可知旎假口己) 一2 ， 又由定理1 3 5 可知， 化口己) 芝z 化口名) 9 硕士学位论文 m a s t e r st h e s i s m 2 n z 、一 m 2 n 2 2 【( m 一1 ) 厅+ o 一1 ) m 。1 i l - 一竺二丝二堕一 1 ， 暑l) - m 2 n 2 4 r a n + 2 m + 2 ，l 即五( 只口己) 乏2 所以有镌( 只口己) f f i 3 同样的道理，只口c 。中每一个子图均满足它的最小度不超过3 ，那么我们可以 看出如下推论。 推论3 3 以( 只i - - 1c ，) f f i 4 乞口q 证明：假设g = 只口巳，由图g 的构造，可以看出，去掉一个4 度顶点得到的 g 2 有下面事实，6 ( g 2 ) s3 ，并且直到把所有的4 度顶点都去掉后，得到的是一个子 图日，它是由圈和n 条不相关的边可以明晓这个g 的子图有最小度不超过3 ，而且 在每一次去一个4 度点的过程中，日都在剩下的子图中，也就是说得到h 之前的每 一个子图，都满足它的最小度不超过3 。当去掉所有4 度顶点，得到h 后，应继续去 掉h 中3 度顶点，仍然满足在得到的每一个子图中，它的最小度不超过3 ，即图g 符 合定理2 2 4 的所有条件，那么有：放( 只口己) s 4 现在，我们关心的是有没有可能饬( 只口己) j 2 时。对于任意的，e f ( h 。，彳) ，和厂 e ( 日) 对应的任何日上的 a 着色c l ，我们就可以补充定义一个日，上的彳着色c ：y ( h 。) 一彳： 令瓴+ 1 ) = “l ，毛2 ，矗) ，1s ，s 七，如果茗y ( h ) ，令c o ) 一c i o ) ，如果xt + l ， 令c o ) 一口7 ， 其中口么7 = 彳一 c ) + ，“+ 而她一1 ，2 ，r ) 又因为陋i 之七+ 1 ，所 以a 垂从而得到了一个关于日。的o ，厂) - 着色c 也就是说假，h ，) 是彳- 可扩展 的。依次像这样按照顶点标号顺序扩展，一定可以得到( h ，g ) 是a 可扩展的。 推论3 1 2 令k m a x 日5 ( h ) ，其中日是图g 的任一支撑子图，我们可以得出： 1 2 硕士学位论文 m a s 丁e r st h e s l 8 以【g _ ) sk + 1 证明：设阶数为珂的图g 的一个支撑子图序列日。 h 。d ) ，令h 。一g ，按照子 图序列的定义，在吼中取一个顶点设为而使得d 肌o ，) s 七，并假设一。= h ，一x t ， 得到y ( g ) 一仁，石：，z 。，h 。= ( 缸。，巾) 是彳一可着色的，并且每一个工，2sj s 以至 多跟七一l + - 页点x i ，( 2s f s _ ) 相邻，也就是说，每一个z ，2sj fs 一至多跟七个顶点 x i ，0s fs 歹) 相邻，依据定理2 1 1 当然有，( g ) s 七+ 1 根据推论3 1 2 ，我们可以容易看出下面这个推论。 推论3 1 3 令图g 的度序列满足：d ，d ：d 。，则有： x s ( g ) s m a ，x 。m i n d f + l f 换句话说，如果七是使得七s 以+ 1 的最大自然数，那么( g ) s 七 证明饵设y ( g ) = “，v 2 ，以 ，令d 化) = d i ，( 1 fs 刀) ，并令h g 【 ，屯，】，则我 们可以得到有6 ( 日) s 哦并且同时有6 ( h ) s f 一1 成立，所以6 ( h ) = m i n d ；，i 一1 ，因为 h = g k ，x 2 ，】，( 1s fs 咒) 是g 的一个支撑子图，这时我们可以取七= m a x 日6 ( h ) ， 即七= m a x 日m i n d i ，i 一玳 则根据推论3 1 2 ，我们不难得到：g ( g ) m a ：x 。m i n d ；+ 1 m 推论3 1 4 ( g ) si g l + l - x g ( 动 。 证明：令图g 的度序列满足：d 。苫d ：d 。，那么万的度序列满足： 五五苫五，其中 互一刀一d + l 一 将k 记作是使得ks d 。+ 1 的最大自然数，由推论2 1 3 得， 硕士学位论文 m a s t e r st h e s i s 以( g ) + ( g ) s 七+ m i a x m i n n d n + l _ i , i = k + 咒+ 1 一r e i n m a x d 。+ l 。+ l n + 1 - i = n + 1 + 七一r a i n m a x d f + 1 f ) s n + 1 以上两个推论，推论2 1 3 和推论2 1 4 都可以验证下面这个在第一节中已经 知道的结论。 推论3 1 5 对于任意的图g ，有 以( g ) s ( g ) + 1 3 2 主要结论证明 定理3 2 1 ( 定理3 1 ) 令数苫3 ，图g 满足：( g ) 墨a ，并且k ca ，那么 有 讫( g ) s a 证明：当( g ) 时，由推论3 1 5 可得， 磊( g ) s ( g ) + 1 s a - 1 + 1 = a 当( g ) = 时，则一定有l g l a + 1 如果l g i a + 1 ，不妨设x e v ( a ) ，d 0 ) 二，那么a ( a 一工) s 一1 ，又因为 h = g x 不是完全图，所以磊俾) sa - 1 先给定g 一个定向j d ，p i a ，每一条 边p2 x j 的定向是由t 发向x ，的，当b 时。对于任意的，f ( g ，爿) ，i ( 日) 对 应的任何日上的彳一着色c l ，我们可以补充定义一个g 上的彳一着色c ：y 俾。) 彳： 令o ) = 缸n ，薯2 ，工迅) ，如果v e v ( h ) ，令c ( o c 。p ) ，如果y x ，令 c ) 一口， 其中口彳一彳一 c ) + ，g ) 防一1 ，2 ，) 又因为z 譬( 日) s 一1 ，所 以彳垂，从而得到了一个关于g 的似，) 一着色c 1 4 硕士学位论文 m a s t e r st h e s i s 如果l g i a + 2 ，不失一般性，可以假设g 是2 一连通的。如果g 中存在一个顶 点工，d o ) ，那么根据g 的连通性可知g 的顶点可以排列成如下序列： x n = x ) x “，x 。，并且满足，每一个顶点以，k n 都和排在前面的至少一个顶点相 邻。则由推论3 1 2 得，以( g ) sa 那接下来，我们只要证明当g 是一正则的情 况下，以( g ) s 成立。 让我们先来证明下面这个事实，在图g 中，一定存在这样两个顶点a 和b ，使得 d ( a ，b ) 一2 并且g a b 是连通的图。如果g 中存在某个顶点y 使得g y 是2 一连 通的，这上述结论显然成立。如果g y 是可分的，我们可以取g y 的两个分块b 和占：，由于g 是2 一连通的，就一定存在一个顶点口且n 0 ) ，和另一个顶点 b e b ：n n ( y ) ，使得它们不成为g y 的割点，即g y ab 仍是连通的。那当然， g 一口一易也是连通的，又因为口和b 都是y 的邻点，d ( a ，6 ) = 2 像前面说明的一样，由于g a b 是连通的，所以她的顶点可以排列成如下 序列：x 。= y ，y 。，y ，并且满足，每一个顶点y 。，七 d 化) d 心) g = g l 口g 2 ，y ( g ) = ) ，l ais 以；1s j sm 那么我们可以清楚的知道 ( g ) ；d “t ) ，6 ( g ) = d ) 将子图g 【“i j 一1 ，2 ，小) 】简记为g l ，子图 a h x , - | f = 1 , 2 ，靠】简记为g ，易知在d ，fe f ( a ，爿) 下，g l ，有一个似，i ( g ) 一可 着色c l ，g ，有一个即，厂i e ( g ：f i ) ) 一可着色c 2 ，令g 1 = g 1 ，ug i l ，翟e d - - f ，我们这样定 义函数c ( 1 ) ： c x l j ) 鼻c i ( 工1 j ) ，1sj si n ； c 1 瓴1 ) = c 1 瓴1 ) + c 1 “1 ) 一c 2 瓴1 s fs 以 上述函数就是g 1 = g , j u g l 在d ，f ( g ，么) 下的一个似，l e ( g m ) ) _ 可着色：因 为以( g 1 ，) s 七l ，x g ( g j l ) s 七2 ，所以以( g 1 ) sm a x 2 1 ，k 2 ) = 七假设下一个着 色顶点为嘞，( 2s fs 以；2s _ s 臃) ，则嘞至多与黾，0s fs j 一1 中j 一1 个顶点相 邻，但它又至多与：o ss f 一1 中f 一1 个项点相邻，所以我们可以给c o ( 砀) 赋值， 令，一 c u 哪k ，) ；厂，) ，p ，( ( 嘞) ) n 1 ，2 ，。j 一1 ) ) ，c a 哪纯冉) + ，嘞而坷) ， 心，( ”n 扎2 ，j 一1 ) ，又因为d ( x dsd 瓴，) ，所以集合彳一，肯定不是空集， 其实，d 嘞) s 七，要不然，会存在一个着色，使得而，在彳中找不到一个颜色可以赋 1 6 硕士学位论文 m a s t e r st h e s i s 值。即当j 走遍所有的m 时，我们可以得到一个在d ，f f ( c ，彳) 下的一个 似，厂i e ( g m ) ) 一可着色，当我们的f 等于以时，那就表示所有的顶点都已经被着色，所 以我们得到一个在定向d 下，图g = g l 口g 2 的一个，) 一可着色c f c ( 1 ) 嘞) ，当f - - 埘3s sm ； c ( x , j ) = c ( 1 嘞) ，匈t 埘，1 sis n ； p ) ，2 sis 刀，2s j s 朋 综上所述，g 1 口g 2 是彳一可着色的，陋i 乏七+ 1 即 旎( g l 口g 2 ) s k + 1 = m a x x g ( g 1 ) ，讫( g 2 ) + 1 = m a x 玩( g 1 ) + 1 ，以( g 2 ) + 1 1 7 硕士学位论文 m a s t e r st h e s i s 结束语 本文主要研究了图的群着色数的一般结论，并将这些结果概述出来。图的一般着 色是由给地图着色等这些实际问题出发而研究得到的。群着色理论就是将k 种着色 推广到阿贝尔群着色的这样一个更广泛数学问题中来研究的，我们不难想象这两种 近似理论的相关性。阿贝尔群的阶数好像是群着色的一个指标，图越复杂，需要着 色的阿贝尔群阶数越大，但是有可能此图一般着色数却远远小于群的阶数。从文献 中我们知道简单平面图的群着色数不超过6 ，而这个简单平面图的一般着色数就很 有可能等于群着色数。也就是说，并不是所有关于图的一般着色结论都可以推广到 图的群着色结论。比如说关于图的笛卡尔积g ，口g ，图g ，和g ，都是本文中规定的 简单无环图，z ( q 口g 2 ) sm a x 仅( g 1 ) + 1 , x ( g 2 ) + 1 ) ，但是在群着色中，此结论是否 仍然成立呢? 作者做了一个小研究，结论在群着色中仍然成立，但是作者认为本文 中方法不是很优，希望能够得到更好的指导。 1 8 参考文献 1 r b r o o k s ，o nc o l o u r i n gt h en o d e so fan e t w o r k ，p r o c c a m b r i d g ep h i l s o c 3 7 ( 1 9 4 1 ) ，1 9 4 1 9 7 2 h 一j l a ia n dx k z h a n g ，g r o u pc o l o r a b il i t yo fg r a p h s ，a r sc o m b i n a t o r i a ， 6 2 ( 2 0 0 2 ) ，2 9 9 3 1 7 3 b o n d y ，j a ，m u r t y ，u s r g r a p ht h e o r yw i t h a p p li c a t i o n s ，a m e r i c a n e l s e v i e r ，n e wy o r k ，1 9 7 6 4 f j a e g e r ，n l i n i a l ，c p a y a n ，a n dm t a r s i ，g r a p hc o n n e c t i v i t yo fg r a p h s a n o n h o m o g e n e o u sa n a l o g u eo fn o w h e r e z e r of l o wp r o p e r t i e s ，j c o m b i n t h e o r ys e r i e sb5 6 ( 1 9 9 2 ) ，1 6 5 1 8 2 5 g s z e k e r e sa n dh s w i l f ，a ni n e q u a l i t yf o rt h ec h r o m a t i cn u m b e ro fa g r a p h ，j c o m b i n a t o r i a lt h e o r y4 ( 1 9 6 8 ) 卜3 6 6 h 一j l a i ，x l i ，a n d g e x i ny u ，o nb r o o k s c o l o r i n gt h e o r e m ， d e p a r t m e n to fm a t h e m a t i c s ，w e s tv i r g i n i au n i v e r s i t y ，m o r g a n t o w n ，w v ， 2 6 5 0 5 7 h 一j l a i ，x k z h a n g ，g r o u pc o l o r a b i l i t y o fg r a p h s ，d e p a r t m e n to f m a t h e m a t i c s ，w e s tv i r g i n i au n i v e r s i t y ，m o r g a n t o w n ，w v 2 6 5 0 5 8 z h c h e n ，h - j l a i ，x l e i a n dx k z h a n g ，g r o u pc o l o u r i n g a n dg r o u p c o n n e c t i v i t y o f g r a p h s ， ( w i t hc h e n ，l e i a n dz h a n g ) ， c o n g r e s s u s n u m e r a n t i u m ，1 3 4 ( 1 9 9 8 ) ，1 2 3 1 3 0 9 n k r a l ，0 p a n g r a c ，a n dh j v o s s ，a n o t eo ng r o u pc o l o r i n g s ，j g r a p h t h e o r y ，5 0 ( 2 0 0 5 ) ，1 2 3 - 1 2 9 1 0 h 一j l a i a n dx l i ， g r o u p c h r o m a t i cn u m b e ro fg r a p h ，g r a p h sa n d c o m b i n a t o r i c s ，2 1 ( 2 0 0 5 ) 4 6 9 4 7 4 1 1 h 一j l a ia n dx l i ，g r o u pc h r o m a t i cn u m b e ro fp l a n a rg r a p h sw i t hg i r t h a tl e a s t4 ，j g r a p ht h e o r y ，5 2 ( 2 0 0 6 ) 5 1 7 2 1 2 h 一j l a i ，x l i a n dg y u ，a ni n e q u a li t yf o rt h eg r o u pc h r o m a t i cn u m b e r o fa g r a p h ，d is c r e t em a t h ，3 0 7 ( 2 0 0 7 ) 3 0 7 6 3 0 8 0 1 3 b l i ua n dh - j l a i ，m a t r i c e si nc o m b i n a t