（基础数学专业论文）非负特征图的非正常染色.pdf

摘要 摘要 本文主要研究非负特征图的几类染色问题：非正常染色、线性染色 及无圈边染色 图g 的一个( 点) 染色是从顶点集合y ( g ) 到颜色集合s 的一个映射 c ，其中s 中的元素称为颜色，染相同颜色的顶点构成一个色类如果 i s i = k ，则称c 是图g 的一个k 染色，通常s = 1 ，2 ，尼) 如果图g 的 一个k 染色使得图g 的相邻顶点都染不同的颜色，则称这样的染色是正 常染色如果图g 存在一个正常忌染色，则图g 称为忌可染的图g 的点 色数是使得图g 存在正常染色的最小颜色数，记为) ( ( g ) 显然，图g 的点 色数总是存在，因为总可以给图g 的每个顶点各自不同的颜色，从而得到 图g 的一个正常i v ( c ) | - 染色 列表染色是顶点染色的一个推广，这种染色对于图的每个点可选用的 颜色有一定限制列表染色最初由v i z i n g 及e r d 6 s ，r u b i n 和t a y l o r 提出图 g 的一个点列表分派l 是指给图g 的每个顶点u 一个颜色集合l ( u ) 给定 图g 的一个列表分派厶如果图g 存在一个正常染色西使得每个顶点所 染的颜色均选自各自的颜色集合l ( u ) ，则称图g 是l 可染的或称妒是图 g 的一个l 染色如果对于任意给定的图g 的列表分派l 且每个顶点的 颜色集合i l ( v ) i = k ，图g 都存在正常染色，则称图g 是k 可列表染色或 k 可选色的 我们要讨论的第一种染色问题称为非正常染色( i m p r o p e rc o l o r i n g ) 图g 被称为是( k ，d ) + 可染的，如果能用忌种颜色对图g 的顶点染色， 并且使得每个顶点的邻点中至多只有d 个与自己染相同的颜色显然，图 g 的( k ，0 ) + 染色即为正常染色对于给定的列表分派厶图g 的( l ，d ) + 一染 色是指图g 的顶点可以l 一染色，并且每个顶点的邻点中至多只有d 个与 摘要 自己染相同的颜色如果对于任意的列表分派己满足每个点的列表集合 i l ( u ) l 均为忌，图g 都存在一个( 厶d ) + - 染色，则称图g 是( k ，d ) + - 可选的上 述的非正常选色的概念由k r e k o v s k i ，e a t o n 和h u l l 提出 在第二章，我们将对可嵌入曲面图的( k ，d ) + - 选色做一些研究具体 的，我们得到如下的结论： ( 1 ) 每个不含4 一圈和8 一圈的平面图是( 3 ，1 ) + 一可选色的 ( 2 ) 每个不含4 圈和9 一圈的平面图是( 3 ，1 ) 可选色的 ( 3 ) 每个不含3 圈和4 - 圈的轮胎图是( 3 ，1 ) + - 可选色的；每个不含3 一 圈和6 圈的轮胎图是( 3 ，1 ) 幸可选色的；每个不含4 圈和6 圈的轮胎图是 ( 3 ，1 ) + 可选色的 ( 4 ) 每个不含相邻3 图和5 圈的轮胎图是( 3 ，2 ) + 可选色的 ( 5 ) 每个不含3 一圈的轮胎图是( 3 ，2 ) + 一可选色的 另外一种我们所关注的染色问题是线性染色( l i n e a rc o l o r i n g ) 图g 的线性染色是一个正常染色满足任何两种色类的导出子图是一 些不交路的并图g 的线性染色数是图g 存在线性染色的最少颜色数，记 为f c ( g ) 文献【4 0 中已经证明如下结论：每个平面图g ，若存在一个有序对 ( ，g ) ( 1 3 ，7 ) ，( 7 ，9 ) ，( 5 ，1 1 ) ，( 3 ，1 3 ) ) ，使得x ( c ) 且g ( a ) g ，则 l c ( g ) = r 必21 i + 1 文献【4 0 】还证明了每个平面图g ，如果夕( g ) 6 ，则f c ( g ) 学1 + 4 ；如果9 ( c ) 5 ，则i c ( g ) r 业2 i + 1 4 在第三章中，我们将得到平面图的线性染色的一些改进的界我们证 明了如下结论： 摘要 ( 1 ) 如果g 是围长至少为8 的平面图，则f c ( g ) 竽1 + 2 ( 2 ) 如果g 是围长至少为6 的平面图，则z c ( a ) 竽1 + 3 ( 3 ) 如果g 是围长至少为5 的平面图，则z c ( a ) r _ l 2 q l l l + 1 0 第三类我们要讨论的染色问题是图的无圈边染色问题( a c y c l i ce d g e c o l o r i n g ) 图g 的一个( 边) 染色是从边集合e ( g ) 到颜色集合s 的一个映射c ，其 中s 中的元素称为颜色，染相同颜色的边构成一个色类如果f s i = k ，则 称c 是图g 的一个七边染色如果图g 的一个k 边染色使得图g 的相邻 的边都染不同的颜色，则称这样的边染色是正常边染色如果图g 存在一 个正常七边染色，则图g 称为忌边可染的图g 的边色数是使得图g 存 在正常边染色的最小颜色数，记为x 7 ( g ) 显然，图g 的边色数总是存在， 因为总可以给图g 的每条边各自不同的颜色，从而得到图g 的一个正常 i e ( g ) i - 边染色 图g 的无圈边染色是图g 的一个正常边染色满足在这种边染色下不 出现双色圈图g 的无圈边色数是使得图g 存在无圈边染色的最小颜色 数，记为乜，( g ) 在第四章，我们证明了如下结论i ( 1 ) 每个平面图g ，若存在一个有序对( ，夕) ( 8 ，7 ) ，( 6 ，8 ) ， ( 5 ，9 ) ，( 4 ，1 0 ) ，( 3 ，1 4 ) ) ，使得a ( a ) a 且9 ( g ) g ，则q 7 ( g ) = ( g ) ( 2 ) 每个平面图g ，如果g ( a ) 4 ，则q 7 ( g ) a ( a ) + 5 文章的最后，我们提出了一些可进一步研究的问题 关键词：染色，非正常染色，线性染色，边染色，无圈边染色，平面图，色数， 轮胎图，列表染色 a b s t r a c t a b s t r a c t i nt h i sd i s s e r t a t i o n ，w ei n v e s t i g a t em a i n l ys o m eg e n e r a l i z e dc o l o r i n gp r o b l e m so fe m b e d d e dg r a p h sw i t hn o n n e g a t i v ec h a r a c t e r i s t i c 。 a ( v e r t e x ) c o l o r i n go fag r a p hgi sam a p p i n gc ：v ( g ) _ s t h e e l e m e n t so fsa r ec a l l e dc o l o r s ；t h ev e r t i c e sr e c e i v i n gt h es a m ec o l o rf o r ma c o l o rc l a s s i f 吲= 忌，w es a yt h a tci sak - c o l o r i n g ac o l o r i n gi sp r o p e r i fa d j a c e n tv e r t i c e sh a v ed i f f e r e n tc o l o r s ag r a p hi sk - c o l o r a b l ei fi th a sa p r o p e rk - c o l o r i n g t h ec h r o m a t i cn u m b e r ) ( ( g ) i st h el e a s t 七s u c ht h a tg i sk - c o l o r a b l e o b v i o u s l y , x ( a ) e x i s t sa sa s s i g n i n gd i s t i n c tc o l o r st ov e r t i c e sy i e l d s ap r o p e ri v ( c ) l c o l o r i n g l i s tc o l o r i n gi sag e n e r a l i z a t i o no fv e r t e xc o l o r i n gi nw h i c ht h es e to fc o l o r s a v a i l a b l ea te a c hv e r t e xi sr e s t r i c t e d t h i sm o d e lw a si n t r o d u c e di n d e p e n d e n t l y b yv i z i n g ，a n db ye r d 6 s ，r u b i na n dt a y l o r al i s t - a s s i g n m e n tl t ot h ev e r t i c e s o fgi sa na s s i g n m e n to fas e ti ( v ) o fc o l o r st ov e r t e xvf o re v e r yv y ( g ) i fgh a sap r o p e rc o l o r i n g 妒s u c ht h a t 矽( u ) i ( v ) f o ra l lv e r t i c e s 口，t h e n w es a yt h a tgi sl c o l o r a b l eo r 西i sa nl c o l o r i n go fg w es a yt h a tgi sk l i s tc o l o r a b l e ( o rk c h o o s a b l e 、i fi ti sl - c o l o r a b l ef o re v e r yl i s t a s s i g n m e n tl s a t i s f y i n gl ( u ) i = 忌f o ra l lv e r t i c e s 口 t h ef i r s te x t e n s i o no fc o l o r i n gw ea r ec o n c e r n i n gw i t hi sc a l l e di m p r o p e r c o l o r i n g g i v e ni n t e g e r ska n dd ，ag r a p hgi s 七一c o l o r a b l ew i t hd e f i c i e n c yd ，o r s i m p l y ( k ，d ) * - c o l o r a b l e ，i ft h ev e r t i c e so fgc a nb ec o l o r e dw i t hkc o l o r ss o t h a te a c hv e r t e xh a sa tm o s tdn e i g h b o r sr e c e i v i n gt h es a m ec o l o ra si t s e l f a ( 南，0 ) * - c o l o r i n gi s a no r d i n a r yp r o p e rk - c o l o r i n g g i v e nal i s ta s s i g n m e n t 一1 1 1 a b s t r a c t l ，a nl c o l o r i n gw i t hd e f i c i e n c yd ，o ra n ( l ，d ) * - c o l o r i n go fg ，i sam a p p i n g ：v ( a ) 一u u v ( a ) l ( v ) s u c ht h a t 砂( u ) l ( v ) a n de v e r yv e r t e xh a sa tm o s t dn e i g h b o r sr e c e i v i n gt h es a m ec o l o ra si t s e l f ag r a p hgi sc a l l e d ( k ，d ) + 一 c h o o s a b l e ，i ft h e r ee x i s t sa n ( l ，d ) * - c o l o r i n gf o re v e r yl i s ta s s i g n m e n tlw i t h i l ( u ) l = kf o ra l lv y ( g ) t h ec o n c e p to fl i s ti m p r o p e rc o l o r i n gw a sf i r s t i n d e p e n d e n t l yi n t r o d u c e db ys k r e k o v s k i ，a n db ye a t o n a n dh u l l i nc h a p t e r2 ，w ew i l lf o c u so nt h e ( k ，d ) * - c h o o s a b i l i t yo f e m b e d d e d g r a p h s a c t u a l l y , w ep r o v et h ef o l l o w i n g s ： ( 1 ) e v e r yp l a n eg r a p hgw i t h o u ta n yc y c l e so fl e n g t hi n 4 ，8 ) ，i s ( 3 ，1 ) * - c h o o s a b l e ( 2 ) e v e r yp l a n eg r a p hgw i t h o u ta n yc y c l e so fl e n g t hi n 4 ，9 ) ，i s ( 3 ，1 ) 木c h o o s a b l e ( 3 ) e v e r yt o r o i d a lg r a p h ，w h i c hc o n t a i n sn e i t h e r - c y c l e sn o rj - c y c l e s f o ra n ys u b s e t i ，歹) 3 ，4 ，6 ) ，i s ( 3 ，1 ) + c h o o s a b l e ( 4 ) e v e r yt o r o i d a lg r a p hc o n t a i n i n gn e i t h e ra d j a c e n t3 - c y c l e sn o r5 一 c y c l e s ，i s ( 3 ，2 ) * - c h o o s a b l e ( 5 ) e v e r yt o r o i d a lg r a p hw i t h o u t3 - c y c l e s ，i s ( 3 ，2 ) + c h o o s a b l e t h eo t h e rv a r i a t i o no fc l a s s i cc o l o r i n gw ea r ei n t e r e s t e di ni sl i n e a rc o l o r i n g a p r o p e rv e r t e xc o l o r i n go fag r a p hgi sl i n e a ri ft h eg r a p hi n d u c e db yt h e v e r t i c e so fa n yt w oc o l o rc l a s s e si st h eu n i o no fv e r t e x d i s j o i n tp a t h s t h el i n e a r c h r o m a t i cn u m b e rl c ( g ) o ft h eg r a p hgi st h es m a l l e s tn u m b e ro fc o l o r si na l i n e a rc o l o r i n go fg i tw a sp r o v e d 【4 0 】t h a te v e r yp l a n eg r a p hgw i t hg i r t hga n dm a x i m u m i v a b s t r a c t d e g r e ea h a sl c ( g ) = f 学 + 1i fgs a t i s f i e so n eo ft h ef o l l o w i n gf o u rc o n d i t i o n s ：( 1 ) g 1 3a n d 3 ；( 2 ) g 1 1a n d 5 ；( 3 ) g 9a n d a 7 ；( 4 ) g 9a n d 7 a l s o ，t h e yp r o v e dt h a tf o re v e r yp l a n eg r a p h ， f c ( g ) 垒笋 + 4i f g ( g ) 6 ，z c ( c ) 。f a _ l 2 盟7 + 1 4i f g ( g ) 5 i nc h a p t e r3 ，w ew i l lp r e s e n ts o m eu p p e rb o u n d so nt h el i n e a rc o l o r i n go f p l a n eg r a p h sw i t hr e s p e c tt oi t sg i r t h ，w h i c hi m p r o v es o m ek n o w nr e s u l t s i n c o n c r e t e ，w ew i l lp r o v et h ef o l l o w i n g s ： ( 1 ) l e tg b eap l a n eg r a p hw i t hm a x i m u md e g r e e i fg ( g ) 8 ，t h e n i t ( c ) s 学1 + 2 ( 2 ) l e tg b eap l a n eg r a p hw i t hm a x i m u m d e g r e ea i fg ( g ) 6 ，t h e n z c ( c ) 学1 十3 ( 3 ) l e tg b ea p l a n eg r a p hw i t hm a x i m u md e g r e e i fg ( c ) 5 ，t h e n z c ( c ) r 蛔2 + 1 0 i nc h a p t e r4 ，w ew i l li n v e s t i g a t ea c y c l i ce d g ec o l o r i n go fg r a p h s a n e d g ec o l o r i n go f ag r a p hg i sam a p p i n gc ：e ( g ) 叫s i fi s i = 忌，w e s a yt h a tci sak - c o l o r i n g ( u s u a l l yw es e ts = 1 ，2 ，尼) ) a ne d g ec o l o r i n g i sp r o p e ri fa d j a c e n te d g e sh a v ed i f f e r e n tc o l o r s ag r a p hi sk e d g ec o l o r a b l ei f i th a sap r o p e rk - e d g ec o l o r i n g t h ec h r o m a t i ci n d e xx 7 ( g ) i st h el e a s t 后s u c h t h a tgi sk - c o l o r a b l e o b v i o u s l y , x 7 ( g ) e x i s t sa sa s s i g n i n gd i s t i n c tc o l o r st o e d g ey i e l d sap r o p e rie ( c ) i e d g ec o l o r i n g a na c y c l i ce d g ec o l o r i n go fag r a p hi sap r o p e re d g ec o l o r i n gw i t h o u t b i c h r o m a t i cc y c l e s t h ea c y c l i cc h r o m a t i ci n d e xo fag r a p hg ，d e n o t e db y 0 1 7 ( g ) ，i st h em i n i m u mi n t e g e r 忍s u c ht h a tg a d m i t sa na c y c l i ce d g ec o l o r i n g u s i n gkc o l o r s 一v 一 a b s t r a c t l e tgb eap l a n eg r a p hw i t hm a x i m u md e g r e eaa n dg i r t hg i nc h a p t e r4 ， w ew i l lp r o v et h a t 口7 ( g ) = a ( g ) i fo n eo ft h ef o l l o w i n gc o n d i t i o n sh o l d s ：( 1 ) 8a n dg 7 ；( 2 ) 6a n dg 8 ；( 3 ) 5a n dg 9 ；( 4 ) 4 a n dg 1 0 ；( 5 ) 3a n dg 1 4 w ea l s os h o wt h a te v e r yt r i a n g l e - f r e ep l a n e g r a p ha d m i t sa na c y c l i ce d g ec o l o r i n gu s i n ga tm o s t ( g ) + 5c o l o r s a st h ee n do ft h i sd i s s e r t a t i o n ，w ep r o p o s es o m ep r o b l e m sf o rf u r t h e rr e s e a r c h e s k e y w o r d s ：c o l o r i n g ，i m p r o p e rc o l o r i n g ，l i n e a rc o l o r i n g ，e d g ec o l o r i n g ， a c y c l i ce d g ec o l o r i n g ，p l a n eg r a p h ，c h r o m a t i cn u m b e r , t o r o i d a lg r a p h ，l i s t c o l o r i n g 一v 1 一 c h a p t e rl i n t r o d u c t i o n c h a p t e r 1i n t r o d u c t i o n g r a p ht h e o r yc a nb et r a c e db a c kt o1 7 3 6w h e ne u l e rp u b l i s h e dh i sp a p e r s o l v i n gk 6 n i g s b e r gs e v e nb r i d g ep r o b l e m ：i st h e r eaw a l k i n gr o u t et h a tc r o s s e s e a c ho ft h es e v e nb r i d g e so fk 6 n i g s b e r ge x a c t l yo n c e ? r e c e n t l y ，g r a p ht h e o r yh a sd e v e l o p e di n t oa ne x t e n s i v ea n dp o p u l a rb r a n c h o fm a t h e m a t i c s ，w h i c hh a sb e e na p p l i e dt om a n y p r o b l e m si nm a t h e m a t i c s ，c o m - p u t e rs c i e n c e ，a n do t h e rs c i e n t i f i ca n dn o t s o s c i e n t i f i ca r e a s g r a p hc o l o r i n gp r o b l e m sf o r mo n eo ft h em a i nt o p i c so fg r a p ht h e o r y t h e d e v e l o p m e n to fg r a p ht h e o r yi t s e l fi sc l o s e l yc o n n e c t e dw i t ht h ei n v e s t i g a t i o n o fo n eo ft h em o s ti n t r i g u i n gp r o b l e m s ：t h ef o u rc o l o rp r o b l e m i n19 7 7 ，a f t e r m o r et h a n12 0y e a r s ，t h ef o u rc o l o rp r o b l e mc h a n g e dt ot h ef o u rc o l o rt h e o r e m b u tt h e r ea r i s eal o to fi n t e r e s t i n gp r o b l e m sc o n c e r n i n gg r a p hc o l o r i n g s d u r i n gt h ep r o c e d u r eo fa t t a c k i n gt h ef a m o u sf o u rc o l o rp r o b l e m i nt h i st h e s i s ，w ew i l la d d r e s ss o m ec o l o r i n gp r o b l e m so fe m b e d d e dg r a p h s w i t hn o n n e g a t i v ec h a r a c t e r i s t i ca n dp r e s e n ts o m er e s u l t so nt h e m t h i st h e s i si so r g a n i z e da sf o l l o w s ：w eb e g i nw i t hb a s i cd e f i n i t i o n sa n d i n t r o d u c t i o n so fc o l o r i n gp r o b l e m s i nc h a p t e r2 ，3 ，4 ，w ew i l lm a i n l yp r o v e s o m er e s u l t so ni m p r o p e rc o l o r i n g ，l i n e a rc o l o r i n ga n da c y c l i ce d g ec o l o r i n go f g r a p h s ，r e s p e c t i v e l y w ee n do u rt h e s i sw i t hs o m ep r o b l e m sf o rf u r t h e rr e s e a r c h 1 1s o m eb a s i cn o t a t i o n s u n l e s ss t a t e do t h e r w i s e ，w ef o l l o wt h en o t a t i o n sa n dt e r m i n o l o g yi n 【9 】 一l 一 一 s ! ：2 ：! ! ：2 1 ：i 2 2 一 a g r a p hg i sa no r d e r e dp a i r ( y ( g ) ，e ( g ) ) c o n s i s t i n go fas e tv ( c ) o f v e r t i c e sa n das e te ( g ) ，d i s j o i n tf r o my ( g ) ，o fe d g e s ，t o g e t h e rw i t ha ni n c i d e n c ef u n c t i o n 移gt h a ta s s o c i a t e sw i t he a c he d g eo fga nu n o r d e r e dp a i ro f ( n o t n e c e s s a r i l yd i s t i n c t 、v e r t i c e so fg i fe i sa l le d g ea n d 似a n dva r ev e r t i c e ss u c h t h a tc a ( e ) = u ，秽) ，t h e nei ss a i dt oj o i nua n du ，a n dt h ev e r t i c e sua n du a r ec a l l e dt h ee n d so fe w ed e n o t et h en u m b e r so fv e r t i c e sa n de d g e si ngb y v ( c ) a n de ( g ) ；t h e s et w ob a s i cp a r a m e t e r sa r ec a l l e dt h eo r d e ra n ds i z eo fg ， r e s p e c t i v e l y ag r a p hgi ss a i dt ob ee m b e d d a b l ei nt h ep l a n e ，o rp l a n a r , i fi tc a nb e d r a w ni nt h ep l a n es ot h a ti t se d g e si n t e r s e c to n l ya tt h e i re n d s s u c had r a w i n g i sc a l l e dap l a n a re m b e d d i n go ft h eg r a p h ap l a n a re m b e d d i n ggo fap l a n a r g r a p hc c a nb er e g a r d e da sag r a p hi s o m o r p h i ct og ：t h ev e r t e xs e to fgi st h e s e to fp o i n t sr e p r e s e n t i n gt h ev e r t i c e so fg ，t h ee d g es e to fgi st h es e to fl i n e s r e p r e s e n t i n gt h ee d g e so fg a n dav e r t e xo fg i si n c i d e n tw i t ha l lt h ee d g e so f gt h a tc o n t a i ni t f o rt h i sr e a s o n ，w eo f t e nr e f e rt oap l a n a re m b e d d i n ggo fa p l a n a rg r a p hg a sap l a n eg r a p h ，a n dw er e f e rt oi t sp o i n t sa sv e r t i c e sa n di t s l i n e sa se d g e s t h ec h a r a c t e r i s t i co fac l o s e ds u r f a c e 夕i se q u a lt oy ( g ) i le ( g ) i + f ( g ) lf o ra n y g r a p hg t h a ti s2 - c e l le m b e d d e di n 夕，w h e r ef ( g ) d e n o t e st h e s e to ff a c e so fg t h ee u c l i d e a np l a n e ，t h ep r o j e c t i v ep l a n e ，t h et o r u s ，a n dt h e k l e i nb o t t l ea r ea l lt h es u r f a c e so fn o n n e g a t i v ec h a r a c t e r i s t i c f o ra ne m b e d d e dg r a p hg ，w ed e n o t ei t sv e r t e xs e t ，e d g es e t ，f a c es e t ， m a x i m u m d e g r e ea n dm i n i m u md e g r e eb yy ( g ) ，e ( g ) ，f ( g ) ，a ( c ) a n d6 ( g ) ， r e s p e c t i v e l y f o rav e r t e xu ，d a ( v ) a n dn c ( v ) d e n o t ei t sd e g r e ea n dt h es e to f i t sn e i g h b o r si ng ，r e s p e c t i v e l y ak v e r t e x ( o rk f a c e ) i sav e r t e x ( o raf a c e ) o fd e g r e ek ，ak 一一v e r t e x ( o r 一2 一 c h a p t e rl i n t r o d u c t i o n k - - f a c e ) i sav e r t e x ( o raf a c e ) o fd e g r e ea tm o s tk ，a n dak + - v e r t e x ( o rk + - f a c e ) i sd e f i n e ds i m i l a r l y t w of a c e so fap l a n eg r a p ha r es a i dt ob ea d ja c e n ti ft h e yh a v ea tl e a s t o n ec o m m o nb o u n d a r ye d g e f o rz v ( v ) uf ( g ) ，w eu s e 凡( z ) a n dv k ( z ) t od e n o t et h es e to fa l lk - f a c e sa n dk - v e r t i c e st h a ta r ei n c i d e n to ra d j a c e n tt o z ，r e s p e c t i v e l y f o rf f ( g ) ，w ew r i t ef = 【u l u 2 u n 】i fu l ，乱2 ，u n a r eo nt h eb o u n d a r yo ffi nt h ec l o c k w i s eo ra n t i c l o c k w i s eo r d e r ak - f a c e f = 【乱1 让2 u n 】i sc a l l e da n ( m l ，m 2 ，i n k ) - f a c ei fd ( u i ) = m if o ri = 1 ，2 ，k 1 2c l a s s i c a lg r a p h c o l o r i n ga n ds o m ee x t e n s i o n s a ( v e r t e x ) c o l o r i n go fag r a p hg i sa m a p p i n gc ：v ( c ) 一s t h e e l e m e n t s o fsa r ec a l l e dc o l o r s ；t h ev e r t i c e sr e c e i v i n gt h es a m ec o l o rf o r mac o l o rc l a s s i fi s i = k ，w es a yt h a tci sak - c o l o r i n g ( u s u a l l yw es e ts = _ 1 ，忌) ) ac o l o r i n gi sp r o p e ri fa d j a c e n tv e r t i c e sh a v ed i f f e r e n tc o l o r s ag r a p hi sk c o l o r a b l ei fi th a sap r o p e rk - c o l o r i n g t h ec h r o m a t i cn u m b e rx ( a ) i st h el e a s t ks u c ht h a tgi sk - c o l o r a b l e o b v i o u s l y ，x ( c ) e x i s t sa sa s s i g n i n gd i s t i n c tc o l o r s t ov e r t i c e sy i e l d sap r o p e rl v ( c ) l - c o l o r i n g a no p t i m a lc o l o r i n go f gi sa ) ( ( g ) - c o l o r i n g ag r a p hg i sk - c h r o m a t i ci fx ( c 1 = k o b v i o u s l y , t h e c o m p l e t eg r a p h r e q u i r e s 1 , c o l o r s ，s ox ( ) = 佗t h e n x ( c ) u ( g ) ，w h e r eu ( g ) d e n o t e st h ec l i q u en u m b e r o fg t h i sl o w e rb o u n d i sv e r yl o o s e i n d e e df o ra n yg i v e ni n t e g e r s 庇1 ，t h e r ea r eg r a p h sw i t hc l i q u e n u m b e r 南a n dc h r o m a t i cn u m b e ri f o re x a m p l e ，m y c i e l s k i 【3 9 】g a v eas i m p l e c o n s t r u c t i o no ft r i a n g l e f r e eg r a p h s ( i e w i t hc l i q u en u m b e r2 ) w i t ha r b i t r a r i l y l a r g ec h r o m a t i cn u m b e r l i s tv e r t e xc o l o r i n gi sag e n e r a l i z a t i o no fv e r t e xc o l o r i n gi nw h i c ht h es e t 一3 一 一一一一一三! ：2 ：! 1 2 ：2 1 ：i 2 l 一 o fc o l o r sa v a i l a b l ea te a c hv e r t e xi sr e s t r i c t e d a l i s t - a s s i g n m e n tlo fag r a p hg c o n s i s t so fs e t so fc o l o r sw h i c ha s s i g n s t oe a c hv e r t e xv v ( g ) ap r e s c r i b e dl i s to fc o l o r s 己( u ) al i s t - a s s i g n m e n ti s a