（运筹学与控制论专业论文）关于距离图着色问题的一点研究.pdf

摘要 一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的 理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有 着广泛的应用背景； 距离图是一类重要的无限简单图，设z 是全体整数集，_ d 是一个正整数集，距离图 a ( z ，d ) 是这样的一类图：点集是z ，z ，y 相邻，若l z y i d 。它的染色问题和很多 实际问题有着密切的关系。所谓图g 的正常点着色是指这样一个映射，：v ( 6 1 ) _ c k = ( c 1 ，5 2 。3 o k ，使：vm t j v ( g ) ，。相邻时，有：f ( u ) ，( u ) 。图g 的点色数是 x ( a ) = m i n k ：v ( a ) _ c 1 c 2 ，c 3 c 是图g 的正常着色 ，而图的圆色数是其点色数的 自然推广，v i n c ( ；以星色数引入这个概念。设p ，q 均为正整数，且p 2 q ，图g = ( e ) 的 ( p ，q ) 一着色是指这样一个映射c ：v - 0 ，1 ，2 ，p l ，使：vx y e ，懈。) 一c ( ) 忆q ， 其中恻b = m i n a ，p 一。) 。圆色数址( g ) = i n f p q ：存在图g 的一种( p ，q ) 一着色) 。而 图g 的分式着色c 是从图的独立集族s 到区间0 ，1 1 的一个映射，使对任意点z ，有： 。瓯。sc ( s ) 1 ，而分式色数x ( g ) 为：x f ( g ) = i n ， 。sc ( s ) ：c 为g 的分式着色) 而 且，对任意图g ，有：x ( a ) 曼溉( g ) x ( g ) 。当| d i 3 时，距离图a ( z ，d ) 的点色数、 圆色数、分式色数几乎都得到了圆满的解决。但是，当i d l 4 这方面的结果还不多。另 外，对于其他类型的集合d ，也有一些结果。 本文给出了一类点色数是3 的距离图的具体着色，确定了某些l d | = d 或5 时距离 图的点色数，利用点色数和圆色数的紧密关系，得到了另一类距离图的各种染色数，并 讨论了图的s t a re x t e 7 r e a l 性质。 关健词：距离图，点色数，圆色数，分式色数 a b s t r a c t g e n e r a l l ys p e a k i n g ，t l l ec o l o l i n gp r o b l e mo f t h eg r a p he a r l yo r i g i n a t e sf _ r o n lt h ef a u l o u s f o u r c o l o r p i o b l e m ”t h ec o l o r i n gp r o b l e l nr i o to n l yb eo fi m p o r t a n tt h e o r i t i c a lv a l u e ，h u ta l s o 、h a v i n gc l o s er e l a t i o nt on l a n yp r a c t i c a lp r o b l e l n s s u c h 嬲t i l ec h a n n e la s s i g n m e n tp r o b l c n i o ft i l e c o m l n n n i c a t i o ns y s t e ma n d8 0o n ，b eo fe n t e n s i v ea p p l i c a t i o nb a c k g r o n n d t h ed i s t a n c eg r a p l ii sac l a s so fi n f i n i t es i m p l eg r a p t i ，s u p p s ezb et h es e t , o fa l li n t e g e r sa n d das e to f p o s i t i v ei n t e g e r s ，t i l ed i s t a n c eg r a p h i st i l eg r a p hw i t hv e r t e xs e tzi nw h i c ht w ov e r t i c e s z 、ya r ea d j a c e n ti fl m 一i di t sc o l o r i n gh a s ( ：l o s er e l a t i o nt f ) m a n yp r a c t i c a lp r o b l e m st h e s o c a l l e dp r o p e rv e r t e xc o l o r i n go f t h eg r a p hi sam a p p i n gf ：v ( a ) _ c k = c l ，( 。2 ，c 3 c 。 ，s u c h t h a tf o ra l lu ， y ( g ) ，u u e ( g ) ，( u ) ，( ) t h ec h r o m a t i cn u l n b e ro fgi sn t i n i u u n no f i ns u c ht h a tt h e r ee x i s t sf ：v ( a ) _ 仇= c 1 c 2 ( 1 3 ，c k w h i c hi sap r o p e rc o l o r i n go fg t h ec i r c u l a rc h r o m a t i cn u n i b e ro fa g r a p hi s an a t u ia lg e n e r a l i z a t i o no ft h ec h i o l i t a t k l t t t n 1 ) e i + o fa g r a p h ，i n t r o d u c e db yv i n c eu n d e rt h ei l a l n et h e s t a rc h r o i n a t i cn u m b e i ”o fa g r a p h s u p p o s e pa n dqa r ep o s i t i v ei n t e g e r ss u c ht h a tp 2 q a ( p ，q ) 一c o l o r i n go fag r a p hg = ( 矿e ) i s a i n a p p i n gcf r o mvt o o ，1 ，2 p 1 ) s u c ht a h tl i c ( x ) 一c ( y ) l l p qf o ra n ye d g ex yee 、w h e r e i l a l l p = m i n a p 一。 t h ec i r c u l a rc h r o m a t i cn l m l b e rx c ( g ) o f g 活t h ei n f i m l mo ft h er a t i o s p q f o rw h i c ht h e r ee x i s t ( p ，q ) 一c o l o r i n go fg t h ef r a c t i o n a lc h r o m a t i cn u m b e ro fa g r a p hi s a n o t h e rv a r i a t i o no ft h ec l u o m a t i cn u m b e r af f a c t i n a lc o l o r i n go fag r a p hgi sam a p i ) i n gc f l o ms ( g ) ，t h es e to fa l li n d e p e n d e n ts e t so fg t ot h ei n t e r v a l 0 1 】s u c ht h a t 自k h f ( sj l i b ra l lv e r t i c e sxi ng t h ef r a c t i o n a lc h r o m a t i cn u m b e r 骱( g ) o fgi st h ei n f i m i mo ft , h ev a l u e s sc ( 8 ) o f af r a c t i o n a lc o l o r i n gco fg m o r e o v e r ，x z ( a ) x e ( g ) sx ( g ) f o ra l lg r a p h sw h e n d i 茎3 ，t h ec h r o m a t i cn u m b e r ，t h ec i r c u l a rc h r o m a t i cn u m b e ra n dt h ef r a c t i o n a lc h r o m a t i cn a r i l b e ro ft i l ed i s t a n c eg r a p h sa ( z ，d ) h a v eb e e na h n o s tc o m p l e t e l yd e t e r m i n e db u tt h e r ea e rr i o t n l a n yr e s u l t sa b o u ti tw h e ni d i2 4 s o n l er e s u l t sh a v eb e e no b s t a i n e df o ro t h e rs e t s t h i sp a p e rg i v e sac o n c r e t ec o l o r i n go fs o i n ed i s t a n c eg r a p h sw i t ht h e c h r o m a t i cn u n l b e r3 a n dd e t e r n l i n e st h ec h r o m a t i cn u m b e ro fs o n l ed i s t a n c eg r a p h sw i t h 【d i = 4o r5 o b s t a i i i st h e a b o v ea l ln u l n b e ro fac l a s so fd i s t a n c eg r a p h sw i t ht h ec l o s er e l a t i o nb e t w e e nt h ee h r o n l a ( ，i e n u m b e ra n dt h ec i r c u l a rc h r o m a t i cn u m b e r 、a n dr e s e a e h e st h es t a re x t r e m a l i t yo fs o n i cg r a p h s k e yw o r d s ：d i s t a n c eg r a p h ，c h r o m a t i cn u l n b e r ，c i r c u l a rc h r o m a t i cn u m b e r f a c t i o n a lc h r o m a t j cn u a n l b e r 第一章概论 一般说来，图的着色问题研究来源于著名的“四色问题”，四色问题是图论也许是全 部数学中最有名，最困难的问题之一，所谓四色猜想是指平面上任何一张地图，总可以 用至多四种颜色给每个国家染色，使得任何相邻国家( 公共边界上至少有一段连续曲 线) 的颜色是不同的。这个问题提出之后，很多数学家作了种种有益的尝试，直到1 9 7 6 年，美国的ka p p e l 和w ，h a k e n 借助于高速电子计算机用了1 2 0 0 多个小时，证明了四色 猜想成立。从此，四色猜想成了四色定理。但是，迄今为止，给出四色定理一个无需借助 计算机的证明，仍是一个未获解决的问题。 1 1 问题的提出 若为自然数集，z 为整数集，整数距离图是指这样一类图：g ( d ) = c ( z d ) ，其 中v ( g ) = z d n ，v “，”z ，有：u 、”相邻当且仅当| “一”i d 。这类图也可简称作 距离图。距离图的着色问题最早起源于平面染色问题：给欧氏空间上所有的点染色，使 单位距离的两点颜色不同，最少需要多少种颜色。这等价于确定平面上距离图g ( r 2 ， l ) ( 其中距离集d = f l ) 的点色数。 图g 的正常着色是指这样一个映射，：v ( g ) _ c a = c ，c 2 ，c ，c t ，使：v mf ， v ( g ) ，“，t ，相邻时，有：f ( u ) f ( v ) 。图g 的点色数是g 的所有正常着色中需要颜色的 最小数目，记作x ( g ) ，即) ( ( g ) = m i n k ：v ( g ) _ h ，。2 ，c 3 饥) 是图g 的正常着色 。 对于距离图g ( z 、d ) 的点色数x ( gc z ，d ) ) 通常简记作x ( d ) 。 图的圆着色是其点着色的自然推广( 2 ) ，它最初叫作星着色。设p ，q 均为正整数， 且p 2 q ，图g = ( v e ) 的，q ) - 着色足指这样一个映射c ：v - o ，1 ，2 ，p 一1 ，使： v x y e ，慨) 一 q ) l l p q ，其中恻l p = m m l a l p l a l ，圆色数x 。( g ) = i n f p q ： 存在图g 的一种( p q ) 一着色 。显然，图g 的( p ，1 ) 一着色就是它的普通p 一着色所以， 对任意图g ，有：x 。( g ) 茎x ( g ) ( 1 7 ) ，另一方面，x ( g ) 一】 。( g ) ，从而，有： x ( g ) = x c ( ( ? ) 。 圆着色的另一等价定义是这样的( 2 4 ) ：令c 是长为r 的一个圆，图g 的一个t 一 圆着色是一映射c 。，给图g 的每一点r 分配一段单位长开弧c ( z ) ，使对g 的每一条边 ( z ，y ) ，有：c ( 叫n c ( y ) ：。若g 存在一个p 圆着色，则称g 是一凰可着色的：图 g 的圆色数x 。( g ) 定义为：h ( g ) = i ll ，p ：g 是r 一圆可染色的) 。 交通信号灯问题是圆着色的重要应用之一。考虑设计一个十字路口的交通控制系统， 给每一股交通流分配一段时间，使之通过路口，即出现绿灯，一个完整的交通周期就是 每一交通流都依次获得一次绿灯的时间段假设每次绿灯时闫是一个单位时闯，我们的 目标就是使这个完整交通周期尽可能的短。不难理解，这是与图的圆着色一一对应的。 图g 的分式着色c 是从图的独立集族s 到区闻 0 ，1 】的一个映射，使对任意点z ， 有； 。缸。sc ( s ) 1 ，分式着色c 的值为，sc ( s ) ，而分式色数x s ( g ) 定义为： x ( g ) = 锄，( 。sc ：c 为g 的分式着色 。 与通讯系统的频道分配问题有直接关系的是图的t 一着色问题。图的t 一着色是 从g 的顶点集v 到非负整数集t = m 】，2 的一映射，使：v 。e ，有： 1 ，( 。) 一，( 9 ) i t 。显然，t = o ) 时，t 一着色就是普通的点着色。而且，定义t 一着 色，的跨度为m f ，“) 一，( w ) ，t ，v j ，给定凰g 和集岔t ，g 的丁跨度定义为 s p 2 、( g ) = r r a i n f m a x i f ( u ) 一，( ) i ：地 v 。令盯 = s p , r ( k 。) ，其中k 。表示具有n 个顶 点的完全图，已经证明( 2 3 ) ，对任意集合t ，灏近t 一染色率且( t ) ：= l i r a ，。譬存 在，并且是一个有理数。而且，还有如下结果： 定理1 1 ( f 1 8 j ) 对任意有限非负整数集合t ，若d = t 一 0 ) ，有月( 丁) = x ，( g ( z ，d ) ) 。 可见，t 一染色和距离图的分式着色有着密不可分的联系。 对任意图g ，均有：m n z 扣( g ) v 【g ) 加( g ) sx ，【g ) sx 。( g ) s x 。( g ) 1 = ( g ) ( * ) ， 其中“( g ) 为图g 的团数，a ( g ) 为图g 的独立数。 当d 有限时，确定距离图g ( z d ) 的各种染色数是一个富于挑战性的问题，迄今为 止，已知的结果还不多，与完全解决还相去甚远。 1 2 现有的一些结果 因为，当d 有限时， i d i 十l 为x ( d ) 的平凡上界( 【9 ) ，即x ( d ) 1 d + 1 ，更 一般的，还有：若d 有限，d = d i ，如d ，) ，则：烈_ d ) sr a i n n e a r n “| d n 十1 ) 其中 d “= 也d ： 1 比、i = 1 ，2 ，3 r ) 。当g 型g 。时，有：x ( c ) = x 【g ) ，从而，由g ( r ) 兰g ( 1 ) ，可以得到，当d = r 时，有：x ( r ) = x 1 ) = 2 。由( + ) 式，得：x ，( 驯= x 。( d ) = 2 。 当d = 。，”，q c d ( a ，b ) = 1 时，有：，( d ) = k ( d ) = ( n + b ) 儿a 十b ) 2 j ( 2 】) 。一般情形 下，设d = a ，b + c 具有如下性质： ( 1 ) g c d ( a ，b ，c ) = 1 2 ( 2 ) a b 、c 中至少有一个偶数 目前还有如下结果： 定理1 2 ( 2 1 ) 若d = n ，b ，n4 - 吐0 n 6 ，蚪f ( ，d ) = 1 ，则有： ( 1 ) 当b u = 3 k 时，) ( ，( d ) = x 。( j ) ) = ( ) ) = 3 ； ( 2 ) 当6 一n = 3 k + i 时，x ，( d ) = x 。( d ) = 3 + 1 ( a 十纠，x ( d ) = 4 ； ( 3 ) 当b = 3 k - t - 2 时，x ，( d ) = 。( d ) = 3 + 1 【+ 2 k + 1 ) ，x ( d ) = 4 。 2 1 中还有如下结果： 定理1 3 设d = f “，2 a ( l 一1 ) a ，6 ，其中g c d ( a ，b ) = 1 ，则有： ( 1 ) a = 16 不是m 的倍数时，xr ( d ) = 如( d ) = x ( d ) = m ； ( 2 ) a = i ，b = m k ( k n ) 时，( d ) = x 。( d ) = m + 1 七，x ( d ) = ，n + l ； ( 3 ) a 2 时，x ，( d ) = x 。( d ) = x ( d ) = ? t t 。 由定理1 3 ，不难得到如下推论： 推论1 1 若d = l ，2t ) ，则有： ( t ) t 不是3 的倍数时，x f ( d ) = ) ( ：。( d ) = x ( d ) = 3 ； ( 2 ) t = 3 ( n ) 时，x ，( d ) = x 。( d ) = 3 + i k ，x ( d ) = 4 。 而且，如下定理确定了l d l = 3 时的点色数的全部情形。 定理1 4 ( 1 2 0 ) 若d = n ，b c ) ，o o b ，且a 、b ，e 均为正整数，9 c d ( o ，b ，c ) = l ，则有： i2 “，b ，c 均为奇数； x ( d ) = 4o = 1 ，b = 2 c = o ( m o d 3 ) 或。+ b = c ，一b 0 ( m o d 3 ) ； i3 其他情形 因此，除了i d = 3 时的某些圆色数心( d ) 、分式色数x f ( d ) 之外( 2 ) ，1 d fs3 时 的各种染色数都得到 圆满的解决。 当1 d 1 = 4 时，这方面的现有结果还不多。例如，x ( 1 ，2 ，3 ，4 n ) = 5 ；当d = y 一n ” ) ，z y ，g c d ( x ，y ) = 1 ，( z ，y ) ( 1 ，2 ) ，。，口奇偶性不同时，x ，( d ) = ) ( 。( d ) = x ( d ) = 4 ； z ，y 均为奇数时，x ( d ) = 5 ( 见【1 0 ) 。当d = 2 、3 ，s s + u 时，有如下定理： 定理1 5 ( 3 ) 对任意整数“1 0 ，任意整数s t t 2 - - 6 u + 3 ，则有：x ( 2 3 8 + n ) = 3 。 定理1 6 ( 5 】) 若d = 2 ，3 ，s ，3 十2 ) ，则有： “d ) = 4 3 其s = - 他2 情( m 形o d 6 k 定理1 7 ( 嗍) 若d = 2 ，3 ，s ，s + 3 ) ，则有： 3 x ( d ) 3s 13 ( r o o d 9 ) ： 4 s 3 ( r n o d 9 ) 且2 8 5 另外，对于具有其他类型集合d 的距离图g ( z d ) 的点色数，也得到了一些结果。当 p 为全体素数集时，有：x ( i ) = 4 ( i 1 1 ) ，当然，若d p ，有：x ( d ) 茎( p ) = 4 ，有些这 样的集合d ，满足：x ( d ) = 4 。d = 3 或4 时，这恫题得到了解决( m1 1 1 2 i ， 当1 d 【5 时，这一问题的完整性结果并不多。d = f d l d 2 d id l ，i = l 23 时， 有；x ( d ) s4 。若集合d = 1 ，2 ，3 n ) f 、2 m ，_ ) 时，有： ( s4 - 1 mk ( d ) = 7 n ：n ( s + 1 ) m ，( n + 87 _ i b + 1 ) ( s 十1 ) 1 x ( d ) f ( t 1 + , 5 r f l + 1 ) ( s + 1 ) 1 + l ( 1 4 ， 15 ) ，关 于这类集合的点色数，f 1 6 】中还得到了一些结果。 本文在第二章中给出了具有5 圈点色数为3 且 d i = 3 的部分距离图的具体着色， 在第三章中确定了距离集中包含 2 ，3 ) ，且i d = 4 雨f 1 5 时一类距离图的点色数，第四章 中，应用点色数和圆色数的密切关系，求出了另一类距离图的各种染色数，并讨沦了一 些图的8 t a t le z t r e m a l 性质。 注：本文中未加定义的概念参见f 2 8 7 第二章满足i d f = 3 ，点色数为3 且含有5 圈的距离图a ( z ，d ) 的点着色 我们知道，迄今为止，l d f = 3 时，距离图g ( z d ) 的点色数x ( d ) 已经得到全部解 决。但是，对于这类距离圈究竟如何用三种颜色进行染色，却没有给出相应的刻划。给 出此类图的具体点着色，具有重要的实际意义，同时，对于如何确定距离图的点色数， 也有一定的启发。 2 1 几个定理 f 4 中给出了几个定理，其证明都是给出一种合适的具体着色，从而得到点色数x ( d ) 的一个上界。 定理2 1 若d = n2 r s ) ，1 n g c d ( r ，叫= 1 ，则：x ( d ) = 3 此定理给出了含有等腰三角形且1 d l = 3 时所有距离图的点色数。 定理2 2 若d = ns ，t ，g c d ( t 池t ) = 1 、n s t n ，+ s 都是奇数，t 2 s 为偶数， 则：x ( d 1 = 3 定理2 3 若d = n8 ，地g c d ( r ，s ，t ) = 1 ，ns ，t n ， s 0 ，则：x ( d ) = 3 定理2 4 若d = ns ，) ，q c d o 、，s ，t ) = 1 r s ，t n t 。 r ，则：x ( d ) = 3 下一节中运用这种给出具体着色的方法，对某种距离图进行研究，从而可以确定它 的点色数。 2 2 一类距离图的具体着色 我们以1 d 1 = 3 x ( d ) = 3 ，且含有5 圈的某些距离图a ( z ，d ) 的点着色为例进行研 究，进而，给出此类图的具体点着色。 在进行研究之前，先给出两个定义。 定义2 ，1 设映射，：z _ g ( 其中i v f = k c 为颜色集) 是距离图a ( z ，d ) 的a 一着色， 若f ( i ) = ，( z + 奶，vi z ，则称，是周期着色，周期为p 。 定义2 2 设映射，：z 斗c 是距离图g ( zd ) 的着色，m ，若，( z + m ) ，f i ) ，v i z ，vm m ，称，足m 相容的。 显然，距离图c ( z d ) 的任一正常着色都是_ d 一相容的，反之亦然。 定理2 1 若d = 2 n3 n 地其中g c d ( 7 1 - t ) = 1 ，t 满足下列条件之- s 寸，有：x ( d ) = 3 ( 1 ) t ik ( m o d 6 r ) ，2 r 4 7 ：( 2 ) t ik ( m o d 6 r ) ，+ 2 r ； ( 3 ) t i k ( m o d 9 r ) ，2 r k 3 ，或6 7 7 r ；( 4 ) t i k o n o d 5 t ) ，2 7 。 k 鼽 证明在距离图a ( z ，d ) 中，点0 ，2 r - ，4 r ，6 r ，3 r 构成一个5 圈，而x ( c 5 ) = 3 ，所以， x ( d ) x ( c , 5 ) = 3 。 下面对各种不同的情形，构造一种相应的周期3 一着色。 ( 1 ) 只= p 6 ，= a 2 r b 2 r c 2 r ：( 2 ) 令a 产= ( a 2 r b 2 t c 2 r ) 。驴，取只：p 3 t _ a 4 眇- 4 ： ( 3 ) 只= p 9 7 = a 2 r b r 2 7 7b 2 7 ：( 4 ) 只= 最r = a 2 r b 2 7 c 7 不难验证，以上各种只都是d 一相容的，从而，x ( d ) s3 ，所以，x ( d ) = 3 ； 注：( 3 ) ，( 4 ) 和( 1 ) ，( 2 ) 的情形既有交叉，又有所不同。例如，当取 只一p g ，= o ”b r c 2 a b 2 ”c ，t ；k ( m o d 9 r ) 、2 7 、 3 7 1 或6 7 1 7 r 时，有： t = 9 r 2 1 + k = 6 r 3 m l + ，( 2 r ，3 r ) ； t = 9 r ( 2 m l + 1 ) + 七= 6 f ( 3 m l + 1 ) + 七十3 7 + 、七十3 r ( 5 r ，6 t ) ： t = 9 r 2 7 n 2 + ：= 6 7 ( 3 m 2 + 1 ) 十k 一6 r ， 一( 0 ，r ) ； t = 9 r ( 2 m 2 + 1 ) + 七= 6 r 。( 3 m 2 + 2 ) + 七一3 7 ， 一3 r ( 3 ，4 2 1 ) 可见，这种情形也蕴涵了tik ( m o d 6 v ) ，0 k ，- 或5 t 。 6 r 的部分情况。 类似的，我们容易得到如下定理。 定理2 2 若d = 协4 r , t ，其e p g c d ( 7 t ，t ) = 1 ，t 满足下列条件之一时，有：x ( d ) = 3 ( 1 ) t 三k ( m o d 5 r ) ，3 ， 砖 4 r ；【2 ) t 三七( 7 n o d l 2 r ) ，8 r 南 l n l ； ( 3 ) t ；k ( m o d 3 r ) 、r 2 r 和0 ，| 证明略 定理2 , 3 若d = ns ，2 ( ，- + s ) 小 s 9 c d ( r 。，s ) = 1 ，当满足下列条件之一时，有： x ( d 1 = 3 ( 1 ) s k ( m o d 3 z ) ，0 r ；( 2 ) d i k ( m o d 3 ，。) ，3 r 2 a 5 7 2 证明在距离图g ( z d ) 中，点0 ，1 2 r ，2 r 1 十s ，2 7 + 2 8 构成一个5 圈，而x ( ( b ) = 3 ， 所以，x ( d ) 23 。 下面只须构造距离图a ( z _ d ) 的正常3 着色即可。 ( 1 ) ，k ( m o d 3 7 ) ，0 女 r 时，令a 少= ( a 2 r b 2 7c 2 7 ) q a ，取周期着色b r h = a ；酏a ! a ：曲； ( 2 ) sik ( m o d 3 7 ) 3 r 2 5 7 2 时，令a 。a b c ，2 = + ( 。bc ”) 。o b 一“2 ，取 玩h 2 = ：翁彪a ：嚣2 4 ；骂，2 。 可以验证，以上的周期着色日和f 3 。h 都是d 一相容的，所以，x ( d ) 曼3 ，即 x ( d ) = 3 。 类似的，我们还可以得到如下定理。 定理2 , 4 若d = ns ，3 ，+ $ ，? - s ，妒d s ) = 1 ，当满足下列条件之一时，有： x ( d 1 = 3 ( 1 ) s 三k ( m o d 3 7 ) ，0 砖 r ：( 2 ) s 三k ( m , o d 3 r ) ，r 1 岛 2 n 定理2 5 若d = ”s ，r + 3 s ，r s ，日c d ( ? ) = = l ，当满足下列条件之一时，有： x ( d ) = 3 ( 1 ) s 三k ( m o d 3 r ) ，0 r ( 2 ) d 三k ( r n o d 3 7 + ) ，r 1 a b 一一b ，则| m7 。n ，使：t = h t a + n b 。 在本章中，我们用基本着色组合的方法，得到距离图的一种着色，确定点色数的个 上界，进而得到它的点色数。第一节中，确定了某些满足 2 ，3 ) cd ，i d l = 4 时的距离图的 点色数) ( ( d ) ，在第二节中，确定了 2 ，3 ，5 cd d 1 = 5 时的某些距离图的点色数( d ) 。 3 1 2 3 ) cd ，i d | = 4 时的某些距离图的点色数 当d = 2 3 ，s 、s + “) 4ss “n 时，除了定理1 5 、定理1 6 、定理17 之外，关 于点色数( d ) 的结论， 5 1 5 中给出了如下定理。 定理3 i 若d = f 2 3 。，口十s ) ，z 3 ，则下列条件之一成立时，有：x ( d ) ：3 ( a ) 5 = l ，z 2 1 ；( b ) s = 4 或5 ，茁 1 7 ；( c ) s = 6 、3 3 1 6 ； ( d ) s = 7 ，z 4 0 ；( e ) s = 8 ，z 9 2 ；( ，) s = 9 ，z 1 9 。 在该定理的证明中，利用尸5 = a a b c c 、r = a a b b c c ，p 9 = a a b c c n b b c 这三种 2 ，3 卜相 容的着色进行组合的。我们可以把b ，尸6 ，p 。等称为基本着色，另外，当1 s 9 且。 2 ，s 3 时，d = n 23 ，z ，。+ s ) ，利用汁算机进行判定，关于点色数x ( d ) ，除了z ( d ) _ 3 的距离图之外，f 5 】中还给出了如下表格，从而确定了所有具有这种类型集合d 点色数 为4 的距离图。 _ _ _ s l45 l j 4 5 6 55 66 ? 4 , 5 ，6 ，1 0 ，1 1 ，1 2 、1 6 ，1 7 ，2 2 8 4 ，5 ，6 ，9 ，1 0 ，1 1 1 3 ，1 5 ，1 8 ，1 9 ，2 3 ，2 4 2 9 ，3 3 ，3 7 ，4 2 ，4 7 9 4 , 5 ，1 0 表1 结合表1 ，注意定理3 1 ，余下的部分可由计算机计算判定x ( d ) = 3 。事实上，可用基 本着色组合的方法来构造距离图c ( z ，d ) 的正常着色，得到x ( d ) 的上界，进而确定x ( d ) 的值。例如，当s = l ，x = 6 即：d = 2 ，3 ，6 7 时，容易验 正p 9 = a a b c c a b b c 是 2 ，3 一相 容的3 着色，取p t = b ，由引理3 ；l ，知：是p 9 是 2 ，3 ，6 。7 卜相容的，即玛是距离图 a ( z ， 2 ，3 6 7 ) ) 的正常3 一着色，从而，有：x ( 2 ，3 ，6 7 ) 3 ；又x ( 2 3 ，6 ，7 ) ( 2 3 ) = 3 ， 所以，x ( 23 6 7 ) = 3 。 观察一下表1 ，不难得到：当n = 6 9 1 0 ，1 1 1 4 时，有：x ( 2 ，3 ，5 ，n ) = 4 。更一般 的，我们可得到如下结论： 定理3 ，2x ( 2 ，3 ，5 ，n ) ： 5 “5 8 ： f4 其他情况 证明由表1 知；当n = 6 9 1 0 ，1 4 时，x ( 2 ，3 ，5 ，n ) = 4 。 由定理1 5 ，知：x ( 2 ，3 ，5 ，7 ) = 4 ，由定理”，知：x ( 2 3 ，5 ，8 ) = 5 。 由引理3 , 3 ，知：x ( 2 ，3 5 ) = 4 ，又x ( 2 ，3 ，5 ，n ) x ( 2 ，3 ，5 ) = 4 。 下面只须构造距离图v ( z ，d ) 的正常4 一着色即可。令9 7 = a a b b c c d ，p s = a a b b c c d d ， 可以验证，p 7 ，p 8 ，p 7 尸8 ，p 8 p 7 都是 2 ，3 ，5 卜相容的。令n = 5 + s ，由引理3 5 ，知：当 s + 3 7 x 8 - 7 8 ，即s 3 8 时，取p t = p ；p ”作为距离图a ( z ， 2 ，3 ，5 ，5 + s ) 的4 一着色，由 引理3 1 ，知：h 是仁3 5 5 + s 卜相容的，从而是正常的，所以，x ( 2 ，3 ，5 ，5 + ，) - 1 、s 3 8 。 当1 5 s + 5s4 3 即9 s 3 8 且s 4 k + j ( k ) 时，由g f 理3 2 ，知：x ( 2 、：355 + s ) s 4 ，下面只须讨论1 0 ss3 8 中, s = 4 k + 3 忙n ) 的情况。s + 5 = n = 1 6 时，取 r = 尸2 l = 聊，由定理3 1 ，知：p t = 局i 是距离图c ( z ， 2 3 ，5 5 + s ) 的正常4 一着色。 1 0 在以下的证明中，将 ：i 时，取h 简记作： = z b = b 。 s + 5 = n = 2 0 最= 毋2 = 辟岛：s + 5 s + 5 = n = 2 8 p f = p 2 3 = j 学p 7 ；s + 5 s + 5 = n = 3 6 日= 马1 = ，瞢b ：$ + 5 马作为距离图g ( z ， 23 5 ， ) 的正常着色 n = 2 4 r = p 2 1 = 聊： “= 3 2 、h = b o = 碍瑶： y t , = 4 0 ，n = p ；8 = 磁辟 所有的情形都已讨论完毕。所以，结论成立。 利用类似的方法，不难得到如下推论。 推论3 1x ( 2 ，3 ，7 川) = 推论3 2x ( 2 ，3 ，8 2 ) = 推论33x ( 2 31 2 ，1 7 , ) f 4n ：9 ，i 0 ： j3 其他情况 f4 ”= 1 l ： 1 3 其他情况 i4 ，l = 1 4 ，1 9 i 3 其他情况 我们还可以得到如下定理。 。、l4 = l l ，1 2 ，1 7 ，2 3 ； 定理3 。3 烈2 13 9 ”1 2 g 其他磊况： 证明由引理3 3 ，知：x ( 2 ，9 ，1 1 ) = 4 ，从而，有：) ( ( 2 ，3 ，9 ，1 1 ) 2x ( 2 、9 1 1 ) = 4 ； 又由引理3 2 ，知x ( 2 ，3 ，9 1 1 ) 4 ，所以，x ( 2 ，3 ，9 1 1 ) = 4 。由引理3 3 和引理 3 4 ，知x ( 3 、9 ，1 2 ) = x ( 1 ，3 4 ) = 4 。 又因为p 7 = a b b c c d 是 2 3 5 卜相容的，由引理31 ，知乃是距离图g ( z 2 、：j ，9 ，1 2 ) 的正常4 一着色。所以，x ( 2 ，3 b ，1 2 ) s4 ，从而，有：3 ，9 1 2 ) = 4 。 由定理3 1 和表1 ，知，n = 1 01 3 、1 4 1 5 ，1 6 ，1 8 时，x ( 2 ，= 39 ，n ) = 3 ，x ( 2 3 9 1 7 ) = 4 。令p 5 = b c c p 6 = c m b b c c ，h 1 = p 5 p 6 ，可以验证屁只1 蜀p 1 1 ，尸1 1 r 都是 2 ，3 、9 ，相 容的。当n 1 8 时，x ( 2 ，3 ，9 ，n ) ) ( ( 2 3 ) = 3 。下面只须构造距离图g ( z ，f 2 ，3 ，9 n 的正 常3 一着色。令9 + s = n ，由引理3 5 和引理3 1 ，可得：当s + 6 。1 1 6 - 6 1 1 = 4 9 即s 4 3 时，只= 刷尸嚣是距离图g ( z ， 2 、3 ，9 ，n ) ) 的正常3 一着色。 = i 9 ，p t = p 2 2 = 磺：n = 2 0 ，只= 岛2 = 硝l ： ”= 2 1 ，只= 岛3 = p 1 l 瑶； = 2 4 。只= = p ； n = 2 5 毋= 民= 尸；： 【谨；n = 2 6 昂= 乃5 = 磁n j ： ? l = 2 7 只= b 6 = 磁：n = 2 8 日= b ( 】= 曹 = 2 9 ，毋= 岛7 = 曲b c ( 。“n b ( ：c b b c ( 1 “胁。曲慨 n = 3 0 、p l p n = p 、j ”= 3 1 。p t = p j 4 = p t p i n = 3 2 ，日= = 磁p l l ：? z = 3 3 辟= p 3 “= 曹 n = 3 4 ，r = p 蝣= 磁：n = 3 5 ，毋= 局4 = f n = 3 6 ，p c = p 3 9 = 硝p 6 ：n = 3 7 ，p = 局o = 瞄絮 n = 3 8 ，r = p 4 0 = 矸i 臻：n = 3 9 p = 一i = 瑶h n = 4 ) p t = p 4 2 = 瑶；n = 4 1 只= p 4 4 = 研 n = 4 2 ，最= p 4 4 一磴：n = 4 3 ，b p 4 5 = 尸矗瑶 n = 4 4 ，只= p 4 1 = 瑶p 】1 ：n 一4 5 p t = 尸4 2 = 磲 n = 4 6 ，r = p 4 4 = p f l ：n 一4 7 ，只= 马5 = p 瑶 n = 4 8 ，p f = p 4 5 = 砰【谨：n = 4 9 好= 娲o ：确璐 n = 5 0 ，毋= p 4 1 = 罐p 1 1 ：= 5 1 ，只= b t = 磲 n = 5 2 ，b = 玮4 = 蜡 下面证明：x ( z ，3 ，9 ，2 3 ) = 4 由引理3 2 ，可得：x ( 2