（应用数学专业论文）关于图的关联色数.pdf

由东科技火学硪士学位论文 摘要 对于图g ，称x ( g ) = ( v ，e ) v ( g ) x e ( g ) iv 与g 棚关联j 为g 的关联集，我们滋g 的两个关联( h 口) 靳( w ，) 是相邻的，当艇仅誉下弼三种情况之一成立 ( 1 )v = w ：( 2 ) e = f ；( 3 ) r 1 4 t = e 或v w = f 图g 的一个关联着色是从关联集i ( g ) 到颜色集c 的一个影射腰，使得x ( g ) 中任何丽 个掇邻懿元素都有不羁懿像。若帮：x ( g ) i - - ) c 是g 的关联着色，且i c i = - 是，女是一个藏整 数，侧称g 鼹女可关联着色的。映射i t 是图g 的一个关联着色，使得g 是七一可关联着 色的最小的k 值称为g 的关联色数。 本文主要研究了图的关联色数。我们在第二章确定了两类平面闰( 花图和棱柱) 的 关联色数：花图的关联色数等于其最大度加1 ；对于棱柱q j ，( n 3 ) ，当撑；0 ( r o o d 5 ) 对， 棱挂灼关联色数等予其最大度热1 ，当是其它情瑟对，棱棱静关联毽数等予其羧大发赭2 。 在第三章我们首先绘怒了匿与其m y c i e l s k i 圈关联色数懿关系：x 孝子任意n 阶蘅g ，如果 它的关联色数等于其最大度翻1 ，那么当它的最大度的2 倍不等予n 时，m ( g ) 的关联色 数等于( 彪( g ) ) + l ，当它的最大度的2 经等予撵时，m ( g ) 豹关联色数枣予等于 a ( m ( g ) ) 十2 ；其次我们还研究了树，最大度5 的h a l i n 图，宪全二部图的m y c i e l s k i 豳的关联色数：设r 为最大度2 3 的树，嬲m ( t ) 的关联色数等子a ( 联 3 ，m 1 ，趟而且唧 都是正整数。 证明：规定，；r ( m o d 厂1 情况1 r 4 考虑颜色集c = 【1 ，2 ，+ 1 。x ：p i = i ，2 r ，令 考虑颜色集c = ( 1 ，2 ，r + l 。对于扛1 ，2 ，r ，令 山东科技大学硕士学位论文 两类平面图的关联色数 a ( u ，“j ) = i ，盯( “f ，“扣) = r + l ，盯( “0 “f “i ) = ( f + 1 ) ( r o o dr ) 盯( “：，u i 川i ) = 盯似；一i ，“川iu j ) + 1 ( r o o dr ) ，盯( “：，“，i “川i ) = 【盯“；，“i “川i ) + 1 】( m o dr ) 盯( v i ，v7 “：一i ) = 仃 二一l ，“：一l v + ) + 2 ( r o o dr ) ，c = 盯 二一l ，“：v i ) 其中j = 2 ，3 ，m i ，“：= ，“：= “。 若n = 2 m - i - 1 ，则着色完毕。 若h 2 m + 1 ，盯( v ，v _ v m i - j “) 至多受三种颜色的限制，而i c | - r + l 5 ，所以存在一 种颜色a ，使得盯( v ，v v 。i - i 。) = d ，其中啦：爪= 吒一：。盯( v ，v 珥) 至多受四种颜色的限 制，而i c b ，+ 1 5 ，所以存在一种颜色，使得盯( v ，v i 一) = 卢。所剩未着色的关联皆为 2 度点的关联，每二关联至多受四种颜色的限制，而i c br + l 5 ，可以对未着色的关联 正常着色。所以盯为f 。的+ l 一关联着色，由引理1 1 知，石( f 州。) = + 1 ( = r 4 ) 。 设 情况2 ，= 3 ( 1 1 ) ，n = 1 ， ，为完全图巧，由引理2 , 2 知，结论显然成立。 ( 1 2 ) m = 2 ，假设e 卫5 存在一个4 一关联着色仃+ ：，( 。，) 一c = 1 ，2 ，3 ，4 ) 。不妨假 盯( “，“f ) = i ，盯( “j ，“- ) = 4 ，其中i = 1 ，2 ，3 。那么盯( n f ，“? v 1 ) = 2 或3 。不妨假设 仃( “f ，“i 1 ，1 ) = 2 ，那么 j + ( v 2 ，v 2 v 1 ) = o - ( v 3 ，v 3 v ) = 2 ， 盯( v 1 ，v v 3 ) = 盯扣2 ，v 2 v 3 ) = 盯+ ( “? ，u ? v 3 ) = 1 ， 口( v 1 ，v 1 v 2 ) = 盯+ ( v 3 ，v 3 v 2 ) = 仃( “? ，u ? v 2 ) = 3 山东科技大学硕士学位论文 两类平面图的关联色数 将没有颜色分配给关联( v 。，v “：) ，其中i = l ，2 ，3 。矛盾。从而石( e - 2 ，) 5 。 下面给出。，的一个5 一关联着色盯；保持上述关联着色的颜色不变添加一种新颜色 5 ，并且令盯( v 。，v 。“f ) = 5 ，其中i = l ，2 ，3 ，综上便得石( 巧25 ) = 5 。 ( 1 _ 3 ) m 3 ，对于f = l ，2 ，3 ，令盯m ，“i ) = i ，o - ( u ，u l u ) = 4 ，口( “：，“f “：) = ( f + 1 ) ( m o d 3 ) ； o - ( u ；，“：“；一。) = 【盯o ；一。，“；一“；) + 1 】( m o d 3 ) ，盯( “；，“i “i 。) = 仃( “；，u ，i u 川i ) + 1 】( m o d 3 ) ，其中 j = 2 ，3 ，m - i ；c r ( v ，v 7 “：一1 ) = 4 ；c r ( v i 2 1 , v 吐1 v ) = 盯( “：- l ，“二一l v 7 ) ，其中“：= ，v o = v 7 ( 2 ) n = 2 m + 2 ( 2 1 ) m = 1 ，令q2 4 ) ，q 。2 2 ( 1 c a ：c a ? 2 2 ) ；e ，2 c a , 2 3 ) 。 ( 2 2 ) ，n 兰2 ，对于i = l ，2 ，3 ， r r ( u ，“j ) = i ，盯0 i ，“ ) = 4 ，盯( “0 “江：) = ( f + 1 ) ( m o d3 ) ； 盯( “j ，“j “；一，) = 盯 ：一。，“j 一，u j ) + 1 ( r o o d3 ) ，盯( “；，“j i “p i 。) = 盯( “；，“，i i ) + 1 】( m o d3 ) ，其中 j = 2 ，3 ，m 一1 ；o ( v i , v i u ：一) = 盯 ：书“：_ 1 y i ) + 1 】( m o d3 ) ，c a , ，= 盯( “：圳“：h v m ； c r ( v ，v v ：) = 盯( v ：，“v 。) ；矿( v ，v v l _ 1 ) = 4 ，其中u 。i = v ，v ? = w ，扩= ，。 ( 3 ) h = 2 m + 3 ( 3 1 ) = 1 ，令c ，= f ) ，其中i = l ，2 ，3 ；c a , = 4 ；c r ( v ，v v f ) = 盯( v 3 ，v 3 v ；) = 2 仃( v 1 ，1 1 1 重) = 0 ( 1 7 2v 2 v j ) = 3 ；盯( v 2 ，v 2 1 ，1 2 ) = o ( v 3v 3 订) = 1 ；盯( v ? 呓) = ( 3 ，4 ) ；盯( v ? ) = ( 1 ，4 ) ； o - 0 32 3 ) = ( 2 ，4 ) 。 ( 3 2 ) m - 2 对于f i l ，2 ，3 ，- 令o - ( u ，u u l ) = i ，盯( “0 u l u ) = 4 ，o - ( u l ，“拟) = ( i + 1 ) ( m o d3 ) ； 9 山东科拄大学硕士学位论文两类平恧罔的关联色数 盯缸；。“；h ：一) = ( 疗o ：圳“j 一u _ ：) + l l c m o d3 ) ，盯( “：，n ；+ ，) = 【盯( “j ，“；一，) 十i ( m o d3 ) ，其中 = 2 3 川一i ，“：= 1 0 ；仃( v 。“0 1 ) = 【盯m 二圳吒。l ) + 1 ( r o o d3 ) 。此时我们显然有 盯( “二巾“0 ，v7 ) l ，2 ，3 。不妨假设盯( “二，“：一。) = i ( 如果不然，我们可以交换颜色) ，那 么c = i j 。 再令盯扣2 ，v 2 e ) = 口 - 2 ) 阶路，则有石c m c 只，= ：荡 乏嚣：i n n = 。2 ， 引理3 3 设r 是一最大度口) 2 的n 阶树，如果2 a ( t ) = , ，要么树丁只有一个最 大度点且它的邻点中至少存在一个叶点，要么树r 含有两个最大度点且其余顶点皆为叶 点。 证明：当2 a ( t ) = ，l 时，若最大度点多于两个，不妨设d ( “) = d ( “：) = d ( u ，) = 口) ， 贝u n d ( u 1 ) + d ( “2 ) + d ( “3 ) 一1 = 3 a ( t ) - i 2 a ( t ) ，矛盾。 ( 1 ) 树丁只有一个最大度点，则在它的邻点中至少有一个叶点。 若最大度点的邻点全是内点，则n 2 d ( u ) + 1 = 2 a ( t ) + 1 2 a ( t ) ，矛盾。 ( 2 ) 树r 含有两个最大度点，则其余顶点全是叶点。 若除了两个最大度点“，v 外还有其它内点。则n d ( “) + d ( v ) + l = 2 a ( t ) + 1 2 a ( t ) 矛盾。 咖s 撇意n 阶配飘郴肛产x 勰： 山东科技大学硕士学位论文 图与其m y c i c l s k i 图关联色数的关系 证明：由m ( g ) 的构造方法知结论成立。 引理3 5 限8 1 对于完全二部图k 一有石( k 。) = m a x m ，n + 2 ，其中m ，n 2 ，且都 是整数。 引理3 6 0 1 设g 为最大度5 的h a l i n 图，则有石( g ) = ( g ) + 1 。 3 2 主要结果 关于图与其m y c i e l s k i 图关联色数的关系，我们有下面的结果： 定理3 1 对于任意，z 阶图g ，如果石( g ) = ( g ) + 1 ，则有 删g 憾豁法勰三： 证明首先对图g 的顶点进行标号，i g ng 的一个最大度点为( 。) + l ，沿顺时针方向， 依次对屹( g ) + 一的邻点标号为h ，v ：，( g ) 。其余顶点顺次标号比( 。) + 2 ，k ( 。) + 3 ， u 即可。 因为疋( g ) = ( g ) + l ，不失一般性，假设存在映射盯+ ：j ( g ) - l ，2 ，( g ) ，( g ) + 1 ) 满足： 盯( 叱( g ) + 】，v ( g ) + 】u ) = f ，仃( u ，v i v a ( g 1 + 1 ) = ( g ) + 1 ，其中f = 1 ，2 ，一，( g ) 。 下面分三种情况把g 的关联着色d + 展至l j m ( g ) 的关联着色仃 ( 1 ) 2 a ( g ) n 由引理3 4 知，( m ( g ) ) = 2 a ( g ) 。考虑颜色集c = c l u g ，其中 2 0 些查壁垫奎兰堡主堂些堡壅 里兰基竺兰! ! ! 坚图茎壁鱼墼! ! 薹墨 g = 【l ，2 ，一，( g ) ，( g ) + 1 ) ，c 2 = f 1 7 ，2 ，一，( g ) ) 为了避免颜色1 7 与7 ( g ) 不同时分配给( f - l ，2 ，n ) 中的关联，我们用下面的方法给 关联集，( m ( g ) ) 、，( g ) 中的关联着色 首先，令盯( q ，u 7 v ) = 矿( v l ，v l v ) ，其中v n ( 5 7 ) n ( 叶) ，i = 1 ，2 ，n 咖伽础g n 二蕃寿篓兰 其次，对于v v ( g ) ，因为 ( v ，w f ，) l u k ( v ) ) k 如( v ) s ( g ) ，而且i c 2 1 ( g ) ， 我们可以用颜色集c 2 中的颜色给关联集( ( u v v f 7 ) i u g ( v ) j 中的关联着色。令 a ( v ，) = i ( m o d a ( g ) ) ，其中v v ( g ) ，且i e 1 ，2 ，( g ) ，( g ) + 2 ，n 。运用这种 方法我们可能遇到以下的矛盾：c r ( v ，n ) = c r ( v ，v v a ( g ) + k ) = k ，其中七f 2 ，3 ，忍一( g ) 】。 如果出现了这样的矛盾，我们将作如下调整： 下面的顶点集合可能为空集，如果某一顶点集合为空集，它所对应情况的关联的颜 色不调整。令顶点v 。与k 。的公共邻点的集合 v = ( v l y e y ( g ) ，v n ( v t ) n n ( v , s + t ) ) ：x u y u z u w 其中x = ( v iv n ( v 1 ) n ( v a ( g ) ) ) y = f v l l ，( 叱( g ) ) 、n ( v 1 ) ) z = v iv en ( v ) n | v ( 叱) ) w = ( v iv 萑n ( v 1 ) u ( ( 6 ) ) le 山东科技大学硕士学位论文 圈与其m y c i e l s i d 图关联色数的关系 对于顶点集合x 中的任一顶点工，把关联f 置以7 ) 的颜色改变为颜色( g ) ，见图3 1 对于顶点集合y 中的任一顶点y ，把关联( 弘) 哌。，。) 的颜色改变为颜色1 ，见图3 2 。，v ， 7 6 c 6 ， v ：。，。 o v y 图3 2 ) ， 对于顶点集合z 中的任一顶点z ，存在一种颜色a 7 没有分配给关联集，：中的任何关 联。显然颜色a 7 c 2 l j a ( g ) ，七，j o 把关联( z ，z ) 的颜色改变为颜色a 7 ，见图3 3 ； 3 4 。 图3 3 对于顶点集合w 中的任一顶点w ，把关联( w ，w v k 7 ) 的颜色改变为颜色，( g ) ，见图 l j 东科技大学硬士学位埝文圈与其m y c i e l s k j 图美联色毁曲关系 罔3 4 假设除了顶点u - - 与v a 。有公共郐点外，顶点与g 。( m 女) 也存在公共邻点 令颚点k 与。铆女) 的公共邻点的集合 y = s is v ( g ) ，j e ( ) n ( 吒l 。h 。) ，m # ) = x7 u y 7 n z u w 其中x 7 = 【v ly en ( v o n ( v 。) y = f v lv n ( v a ) 、n ( v 1 ) z = v i v _ v 如) n ( 叱* ) w = ( v iv # n ( v t ) u n ( v a ( g ) ) l 。 对于顶点集合x n x 中的任一顶点x ，存在一种颜色n 7 没有分配给关联巢t 中豹任 倪关联。显然颜色d c 2 、 1 ：g ) ，七， m 1 。把关联0 w ：) 的颜色玫变为颜色a ，见图 3 5 ： 对于顶点集合x7 、x 中的任一顶点z ，把关联( j ，砜) 的颜色改变为颜色7 ( g ) ，觅 图3 , 6 ； 山东科技大学硕士学位论文 圈与其m y c i e l s k i 图关联色数的关系 v j 。： f g + 图3 5 o v 6 ( g ) + i ( g ) + v a ( g ) + 1 。所以，在不用颜色( ( g ) + 1 ) ，的 山东科技大学硕士学位论文图与其m y c i e l s k i 图关联色数的关系 前提下，可用颜色集c 2 中的其它颜色给关联集( ( v ，叫) t v i v g ( v ) 中所有关联着色，其 中江1 ，2 ，n 。 其次，对于江1 ，2 ，n ，令盯( ”7 ，v f u ) = ( ( g ) + 1 ) ； 咖u 础g n ：三篙0 最后，令a ( w ，p ) = 盯( w ，8 ) ，其中w ey ( g ) ，e ee ( g ) ，且w 与p 相关联。 所以，共用颜色数目为i c 日c li + lc 2 2 ( g ) + 2 = ( m ( g ) ) + 2 ，仃f f r j m ( g ) 的一 个( l f ( g ) ) + 2 一关联着色，因此，疋( 肼( g ) ) ( 肘( g ) ) + 2 。 推论3 1 ：1 对于任意n 研3 ) 阶图g ，如果( g ) = n 一1 ，则有疋( m ( g ) ) = ( m ( g ) ) + l 成立。 证明：显然图g 是完全图蚝的子图，a ( g ) = a ( k ) = n - 1 ，n z i ( k 。) = ( 以) + 1 = ( g ) + 1 ，所以荔( g ) ( g ) + 1 。由引理2 1 知石( g ) = ( g ) + l ，又因2 a ( g ) = 2 ( n 一1 ) n 由定理3 1 知，z ，( m ( g ) ) = ( 肘( g ) ) + 1 。 推论3 i 2 对于任意h 伽3 ) 阶图g ，如果石( g ) = ( g ) + 1 且2 ( g ) n ，则 咒( m ( g ) ) = a ( m ( g ) ) + 1 ，其中，为正整数。 定理3 2 t f f ：2 n ( n 3 ) 阶树，则石( m ( 7 1 ) ) = ( m ( 丁) ) + 1 。 证明当a ( t ) = 2 时，由引理3 2 知结论显然成立。 下面我们证明( r ) 3 时的情况。 些型苎查兰堡主兰些笙塞 望量基竺竖型塑望叁壁皇墼! ! 羞墨 由引理3 1 知，石( 丁) = ( 丁) 十i 。所以当2 a ( t ) n 时，由定理3 1 知结论成立。下面 证明当2 a ( t ) = ，l 时，肘仃) 存在一个( m 叮) ) + 1 关联着色。由引理3 3 ，我们只需要考 虑下面的两种情况： ( 1 ) 树r 只n - - + n n n a ，且在最大度点的邻点中至少存在一个叶点。 对树7 的顶点进行标号，标记最大度点为。，川，标记它邻点中的一叶点为。，对 于其它邻点从h ( n 开始沿逆时针方向顺次标记。m 。，k 。，p 2 v 1 ，树丁中剩余顶 点依次标记v ( 聃2 ，心。 我们首先对树r 进行关联着色，考虑颜色集c l = f 1 ，2 ，a ( t ) + 1 1 ，给出树r 的一个 ( r ) + l 一关联着色矿：，( 丁) _ c j = ( 1 ，2 ，( 丁) + l ，使得对任意的v y ( 丁) 有ic ，1 1 且 当顶点v 不是最大度点时，( r ) 芒c l 。 令o - ( k ( 聃l ，( 聃l u ) = f ，仃+ ( u ，叶( m 1 ) = ( r ) + l ，( f ：1 ，2 ，( r ) ) 。若最大度点 k c r ) + i 的邻点v j ( f _ 1 ，2 ，仃) ) 皆为叶点，则着色完毕。若存在内点，不妨假设u 为内点， n n 关n n ( v , ，v , v ：) iv n ( v 1 ) ，j ( 丁) + 1 ) 中所有关联的数目 ( v 】，v l v s ) iv ，v ( v 1 ) ，( 丁) + 1 ) i = d ( v 1 ) 一1 蔓( r ) 一2 ，i c j | - ( r ) + 1 且关联集f ( u ，u 0 ) i _ ( v 1 ) ，( 丁) + 1 ) 中的任关联现在只受两种颜色的限制，所以 我们可以在不用颜色( r ) 的前提下，n n 色集c , 中的其它颜色依次给关联集 f ( v l ，v i v j ) lv ，n ( v i ) ，( 丁) + l 中的昕有关联着色。重复上述过程直到关联集，( r ) 中的所有关联都着色为止。 下面给出肘( r ) 的一个( 肘( 丁) ) + l - 关联着色d 。 山东科技大学硕士学位论文圈与其m y c i c l s k i 图关联基数的关系 考虑颜色集c = e uc 2 ，其中= ( 1 ，2 ，( 7 ) o ( 7 t ) + i 】，q = 2 ：，a 7 ( r ) 。 令拶( 吖，v ) = 口( - ，b y ) ( 关联瓯旷+ 儿；n ) 除外) ，其中v ，( 0 ) 、 “ ，i = 1 ，2 ， n ；a ( t 巾嵋r ) + i k ) = p ( 小( r ) + i ) 】，= ，( r ) 。 对树7 t 中的顶点v ，因为关联集f ( v ，v ) i u m ( v ) 中所有关联数目 l “v 。v 口i u 坼( 0 1 b 4 ( v ) a 叮) dc 2 l ，所以我们可以用颜色集g 中的颜色绘关联集 f ( n v 一) l u 屿( v ) 中的所有关联着色，且能做到除了最大度点k 。外，可以保证颜色 口) 厶。 i 量铲) + li 厶铲) ， i = a 口) ， i a i f ) + 1 再令茁( v ，v u ) = ( r ) ，其中p 乩。1 ( “) 。 最后令a ( w ，e ) = 矿( w ，e ) ，其中w v ( 丁) ，e e ( r ) ，且w 与p 相关联。 共用颜色数目为i c l = 4c l i + f 仁k 2 a ( t ) + 1 罩( 艏( r ) ) + l 。所瞄，仃是m ( t ) 的一个 ( ( r ) ) + l 一关联着色，所以丑( 肼( 丁) ) 蔓a ( 硝( r ) ) 十l ，由弓 理21 知 的。 石( f ( r ) ) 兰a ( f ( f ) ) + 1 。 ( 2 ) 树r 有两个最大度点，且其余顶点皆为叶点，显然树f 的这辑个最大髓点是相邻 考虑颜色集c = g uc 2 t 其巾c = ( 1 2 。，( r ) ，a ( d + l ，c 2 = ( 1 ， 2 ：，a ( ? ) 。我 们不妨假设 3 2 山东科技大学硬土学位论文 辫与其m y c i e l s k i 墨美联色数的荚系 d r ( s ) = d r ( f ) = ( r ) ，n r ( 5 ) = i ，岛，屯( r 卜，fj ，n r ( t ) = ，t 2 ，。气( r j - j ，s j ，顶点的 标号臻港簇瓣锌方商。 罄先，令 a ( s ，哩 = a 馥，筏) = ，萁串江l ，矗( g ) 一1 ； 箕次，令 c r ( v ，w ) = 矗( r ) + l ，季萋中v m f r ) ( s ) ； a ( v ，v 玲= 矗汀) ， 其中v 0 ( f ) 。 c r ( s ，哟= 拶 s ：s ) = 玎秘，劫一仃 f ：f 气) = 巧0 ，u s 3 = ，其孛f = 】，a ( r ) 一1 ； 盯( h l 峪，) 2 擘( w ，w f ，) = 矗r ) ， 其孛v 7 帮， ) - 矗( 嬲留) ) + l 。 患理3 。3 设g 是簸大度矗5 煞拜( n 是委整数) 除h a l i n 缁，那么 蕞澎( g ) ) = a ( m ( g ) ) + le 谈明：蠢葶| 瑾36 簸五( g 卜矗( g ) 十l ，所以鑫l 定理3 1 我们知道当阏g 的最大度豹2 倍2 a ( g ) n 时，结论显然。 些查堂奎兰堡圭鲎堡笙兰 下嚣我翻必考虑2 a ( g ) = 摊戆壤况。 圈与其m y c i e l s k i 图关联色数的燕累 j 嚣：潜善先考疼h a l i n 垂g 瓣生藏树戆结椽，塞辱l 褒3 3 ，缝合h a t i n 錾熬定义，我髓 知道当2 a ( g ) = h 时，h a l i n 图g 只可能是下面两种情况： ( 1 ) 有一个最大度点。 此种情况h a l i n 图g 的顶点标号我们采用与定理3 2 中的( 1 ) 相同的标号。我们首 先考虑g 的生成树f ，显然有矗( r ) = a ( g ) 。由定瑾3 2 知，存在一关联着色仃： f ( 槲( r ) ) 争c = c l u c j = ( 1 ，2 ，( g ) + l ，1 ，2 i ，a ( g ) ， 其中c l = ( 1 ，2 ，( g ) + 1 ) ，c 2 = l ：2 ，敞g ) l 。由弓l 瑾3 6 ，我们能够用颜色巢c i 中的 蔟色绘委g 戆终都蠢_ 逡器羔兹关联着惫。越辩我靛哭黧关联繁 ( ( 峙，v ( 吐峨) i v y ，e ( g ) 殿f ，1 1 ，2 ，- ，雅”中的关联没有潜色。 令c r ( v , ，k v ：) = 仃( ，蛾) = j ( m o d a ( g ) ) ，其中吒。芒联g ) 。此时可能会存在某一骥 点u 与顶点咋顶点心( 。) 十女都相邻，其中k ( g ) ，则 盯( u ，吒v ：) = c y ( v i ，q v 二( g 卅) = 七；d ( 吐心i ) = a f v ：，v 舨( g m ) = ，矛聪。对于这种情况 我们作如下谪整： c r ( v ，虻。) 在颜色集g 至多受4 粹颜色的限箭，因为l q 譬( g ) 5 ，所以在颜色 集g 旁存在一釉藏色锑，楚缮秽娥，誓+ 。) = 搿。窝捞熬，巧( ，咖：f g ) + k ) 在蕻惩集q 囊 多受4 种颜色的限制，因为i g b ( g ) 5 ，所以在颜色集c 2 巾存在一种颜色多，使碍 仃( 一，v 以( g ) “) = 卢。 若还有类似的情况出现，则可用上述方法进行调擞，直到磁常染色为止。 山东科技大学硕士学位论文 图与其m y c i e l s k i 囝关联色数的关系 ( 2 ) 有两个相邻的最大度点。 此种情况图g 的顶点标号我们采用与定理3 2 中的( 2 ) 相同的标号。与情况( 1 ) 一样， 我们首先考虑图g 的生成树丁，显然有( 丁) = ( g ) 。由定理3 2 存在一关联着色仃： ，( m ( 丁) ) _ c = c l uc 2 = l ，2 ，( g ) + 1 ，1 j 2 7 ，a 7 ( g ) j 其中c j = ( 1 ，2 ，( g ) + 1 ) ，c 2 = ( i ，2 ，( g ) 。由【7 日够用颜色集c j 中的颜色给 图g 的外部面边界上的关联着色。此时我们只剩关联集 f ( ，_ 唾t ) ，( ，毫一毛) ，( ，如) ，( 墨。s l ，。) ，婢，。) ，( 。，。t i ) ，( ，纯，) ，( i 。，o ) 中的关联没有着色，其中f - l ，2 ，( g ) 一1 ，( g ) = ，吆( ，) = ，( ，) = s 0 气( n ：； s o = ( g 卜】，s 02 f ( g ) 一】，= s a 7 ( g 卜】，气= s a ) _ l 。 令q2 气= 气= 气= ( f ，) 其e f l i = l “2 一，( 丁) 一1 。 定理3 4 对于完全二部图k m 一有石( m ( l ，。) ) = a ( m ( k 。) ) + 2 ，其中研，n 2 。 证明：不妨假设，n n ，则( m ( k 。) ) = 2 n 。 设( x ，y ) 是y ( k 。) 的二分划，其中x = ( 玉， ，y = ( y l ，y 。】。，巧分别是， 乃的孪生顶点，其中1 i m ，1 j - 5 的 h a l i n 图的关联色数。本文给出了最大度a 5 的h a l i n 图的m y c i e l s k i 图的关联色数。 2 下述命题是否正确，如果正确给出证明，如果不正确给出反例，或是加上适当的 条件才成立： 且。 对于任意，z 0 3 ) 阶图g ，如果石( g ) = ( g ) + 女( i ) ，石( m ( g ) ) = ( m ( g ) ) + 成 本文的定理3 1 证明了猜想当k = 1 且2 a ( g ) h 时成立，定理3 2 ，定理3 3 ，定理3 4 表明猜想对于三类特殊图成立。但对于一般的图该命题还没有得到证明。 3 确定拟外平面图的关联色数。 设g = ( y ，e ) 是平面图，若g 存在平面嵌入石，使得g 中所有顶点都在石的一个面 的边界上，则称g 是外可平面图，简称为外平面图。给定平面图g ：( y ，e ) ，若存在一外 边p e ，使得g e 是个外平面图( g - e 中所有顶点都与无界面相关联) ，则称g 为 r 垒圣壁垫查兰鋈圭堂笙选奎笾窭堡 揪铃平覆爨。显然任冀步 乎瑟滔赛是拟外平压强。参考文献 i o l 确定了最大度a 4 酌矫 平蘧强静美联色数，等于其最大度黼1 。 4 晦低平蕊图关联色数的上雾。 参考文献【1 6 】给出了平碌图的关联色数的个上界：对于乎蘧图g ，存在一令 g ) + 7 一关联羲色拶，使缮i o - ( & ) | 7 。 山系科技大学碗士学位论文 致谢 在本文的写作过程中，导筛陈东灵教授给予了先私的帮助粕精心静指爵。陈老师程 白忙之中仔细地审阅了全文，提出了很多宝贵的意觅。可以说，本文的每一个缅节里郡 凝聚着陈老师的汗水和心血。陈老师严谨的治举态度，一丝不苟的进取精神使我终身受 益。三年来，陈老师给予了我无微不至的关怀和细心的照顾，使我顺利完成学业。陈老 烀不仅使我学到了科学文化知识，两且使我在为人处世方藤也收获颇丰。谯此，向炼老 魉袭示衷心的感谢秘诚挚熬祝摇。 本文的完残与导溪冻学测老援瓣关心，鼓麓，指导也是密不可分静。蓬嚣为有了蒎 老精静有益指导才使我少志弯路，及辩完成写作。陈老繇诚实髂为人，谦廉好学，雾予 攀髓科学高峰的精神令我敬佩，永远值得我学芍。向陈老筛表示衷心的感谢l 感谢王淑栋老师对我的指导和帮助，感谢信息学院诸使老师的帮助，感谢帮助过我 的同学和亲友。 4 。 尘塞鲢奎羔堡圭篷壁臻奎 叁查茎堂 参考文献 f t 】j 。a b o n d ya n du 。s r m u r t y g r a p ht h e o r yw i t ha p p l i c a t i o n s 【m 】，n e wy o r k ：m a c m i l l a n p r e s s ，19 7 6 【2 】n r o b e r t s o n ，d s a n d e r s ，e s e y m o u ra n dr ，t h o m a s 。t h ef o u r - c o l o rt h e o r e m ：潮，j o u r n a l o fc o m b i n a t i o n a lt h e o r y , 1 9 9 7 ，s e r b7 0 ：2 瓣 【3 】o 。o r e t h ef o u r - c o l o rp r o b l e m m ，a c a d e m i cp r e s s ，n e wy o r k ，t9 7 6 4 】t r j e n s e n ，b t o f t g r a p hc o l o r i n gp r o b l e m s m ，j o h nw i l e y & s o n s 。i n c ，1 9 9 5 ，n e w y o r k 。 【5 】r a b r u a l d ia n dj j qm a s s e y i n c i d e n c ea n ds t r o n ge d g ec o l o r i n g so fg r a p h s j d i s c r e t e m a t h ，1 9 9 3 ，1 2 2 ：5 1 - 5 8 【6 b g r u i d u l i o ni n c i d e n c ec o l o r i n ga n ds t a ra r b o r i c i t yo fg r a p h s j ，d i s c r e t em a t h 。19 9 7 ， 1 6 3 ：2 7 5 2 7 8 【7 】i a l g o ra n d n a l o n t h es t a ra r b o r i c i t yo f g r a p h s j ，d i s c r e t e m a t h ，1 9 8 9 ，7 5 ：1 1 - 2 2 f 8 】陈系灵，麓疆奎，王淑栋图的关联色数和关联着色猜想【j 】，经济数学，1 9 9 8 ，1 5 ( 3 ) ：4 7 5 1 9 1d l c h e n ，r c + b l a ma n dw c s h i u o ni n c i d e n c ec o l o r i n gf o rs o m ec u b i cg r a p h s j d i s c r e t em a t h ，2 0 0 2 ，2 5 2 ：2 5 9 2 6 6 1 0 ls h u d o n gw a n g ，d o n g l i n gc h e r ta n ds h a h c h e np a n g t h ei n c i d e n c ec 0 1 0 f i n gn u m b e r o fh a l i ng r a p h sa n do u t e r p l a n a rg r a p h s j ，d i s c r e t em a t h ，2 0 0 2 ，2 5 6 ：3 9 7 4 0 5 1 1 1 陈学剐，冻东灵，王淑栋路与完全闰的笛卡尔积图和广义圈墨。，的关联色数 j 缀济数学2 0 0 0 ，1 7 ( 3 ) ：4 7 5 i 。 4 l 山东科技大学硕士学位论文 参考文献 f 1 2 陈学剐，王淑栋两类笛卡儿积图的关联色数ij 】，j j j 东矿业学院学报( 自) ，1 9 9 9 ， 1 8 ( 3 ) ：6 5 6 6 ，7 8 1 3 1 陈学刚，陈东灵三类笛卡儿积图的关联色数 j 】，经济数学，2 0 0 2 ，1 9 ( 3 ) ：8 8 9 0 1 4 1 段华，陈东灵1 - 树图的关联色数 j ，山东科技大学学报( 自) ，2 0 0 2 ，2 1 ( 1 ) ： 3 3 3 8 4 1 【1 5 】刘西奎若干图类的对策色数和关联色数【d 】，泰安：山东科技大学，2 0 0 0 【1 6 】m h d o l a m a ，e s o p e n aa n dx d z h u i n c i d e n c ec o l o r i n go f k - d e g e n e r a t e dg r a p h s j 。 m a n u s c r i p t 2 0 0 3 【1 7 】j m c i e l s k i s u rl ec o l o r i a g ed e sg r a p h s ，c o l l om a t h ，1 9 9 5 ，3 ：1 6 1 1 6 2 【1 8 】孟宪勇关于伪一h a l i n 图的几种着色研究 d 】，泰安：山东科技大学，2 0 0 4 1 9 】陈学刚，陈东灵强色指数的一个新的上界【j 】，高校应用数学学报a 辑，2 0 0 2 ，1 7 ( 3 ) ： 2 6 4 2 6 8 【2 0 】k o - w e il i h ，w e i f a nw a n ga n dx u d i n gz h u c o l o r i n gt h es q u a r eo fae m i n o rf r e e g r a p h j ，2 0 0 3 ，2 6 9 ：3 0 3 3 0 9 【2 1 】z h o n g f uz h a n g ，l i n z h o n gl i ua n dj i a n f a n gw a n g a d j a c e n ts t r o n ge d g ec o l o r i n n go f g r a p h s j ，2 0 0 2 ，1 5 ：6 2 3 6 2 6 【2 2 】刘林忠，张忠辅，王建方( g ) 4 的外平面图的邻强边色数【j 】，2 0 0 0 ，1 5 ( 2 ) ： 】3 9 1 4 6 【2 3 】b o r l i a n gc h e n ，c h u n k a nc h e n ga n dh u n g l i nf u as t u d yo ft o t a lc h r o m a t i cn u m b e ro f e q u i b i p a r t i t eg r a p h s j ，19 9 8 ，18 4 ：4 9 - 6 0 2 4 l i n z h o n gl i u ，j i