（运筹学与控制论专业论文）关于极小非圆完美图的若干结果.pdf

a b s t r a c t f o rt w oi n t e g e r s1 d 后，ak - c i r c u l a rc o l o r i n go fag r a p hgi s am a p p i n gc ：y ( g ) h o ，1 k 一1 ) s u c ht h a td l c ( u ) 一c ( 钉) l k dw h e n e v e r 伽e ( g ) t h ec i r c u l a rc h r o m a t i cn u m b e ro fg ， d e n o t e db yx c ( a ) ，i st h el e a s tr a t i o n a ln u m b e r s u c ht h a tt h e r ei s ak - c i r c u l a rc o l o r i n go fg t h ec i r c u l a rc l i q u en u m b e ro fag r a p h g ，d e n o t e db y ( g ) ，i st h em a x i m u m r a t i o n a ln u m b e r s u c ht h a t g _ k a d m i t sah o m o m o r p h i s mt og ag r a p hg i sc a l l e dac i r c u l a r - p e r f e c tg r a p hi fw c ( h ) = x c ( h ) f o re a c hi n d u c e ds u b g r a p hh o fg a g r a p hi sm i n i m a l l yc i r c u l a r - i m p e r f e c ti fi t i sn o tc i r c u l a r - p e r f e c tb u t e a c ho fi t sp r o p e ri n d u c e ds u b g r a p h si s m i n i m a l l yc i r c u l a r - i m p e r f e c t g r a p hi su s e dt os t u d yt h es t r u c t u r eo fc i r c u l a r - p e r f e c tg r a p ha n di t s e e m st h a tt h es t r u c t u r eo fm i n i m a l l yc i r c u l a r - i m p e r f e c tg r a p h si s v e r yc o m p l i c a t e d i nt h i sp a p e r ，w ed i s c o v e rt h a ts o m ef l o w e r su n - d e rc e r t a i nc o n d i t i o n sa r em i n i m a l l yc i r c u l a r - i m p e r f e c t a n ds e v e r a l f a m i l i e so fm i n i m a l l yc i r c u l a r - i m p e r f e c tg r 印h sa r ec o n s t r u c t e df r o m k ，o n eo fw h i c h i sc o n s t r u c t e db yd e l e t i n ga ne d g ef r o mk b u t t h eo p e r a t i o ni sn o ta l w a y ss u c c e s s f u l ，s os o m er e s u l t sa r eg i v e ni n t h ep a p e r a tt h ee n d ，w eg u e s st h a tg 2 吩e f o re i sn o t m i n i m a l l yc i r c u l a r - i m p e r f e t ，i fw c ( g ) = x c ( g ) o rg c o n t a i n sap r o p e r i n d u c e ds u b g r a p hht h a ti sn o tc i r c u a l r p e r f e c t ，a n dhi st h em i n - 2 i m a l l yc i r c u l a r i m p e r f e c tg r a p ht h a tw eh a v ed i s c o v e r e db yd e l e t i n g a ne d g ef r o mk 1 k e yw o r d s ：5 - c i r c u l a rc o l o r i n g ，c i r c u l a rc h r o m a t i cn u m b e r ， c i r c u l a rc l i q u en u m b e r ，c i r c u l a r - p e r f e c tg r a p h s ，m i n i m a l l yc i r c u l a r - i m p e r f e c tg r a p h s 3 摘要 对两个正整数1 d k ，图g 的等圆着色是映射c ：v ( c ) 卜+ o ，1 ，南一1 ) 满足：当u 口6e ( g ) 时，dsi c ( ) 一c ( u ) j k d 图 g 的圆色数，记作x 。( g ) ，是最小的有理数使得图g 存在个圆着色图 g 的圆团数，记作( g ) ，是最大的有理数等满足存在一个从魄到g 的同 态图g 称为圆完美的，若对g 的任意导出真子图日满足“k ( 曰) = x 。( 日) 如果一个图本身不是圆完美的，但它的任意导出真子图是圆完美的，那么我们称 这个囹是极小非圆完美的极小非圆完美图结构的研究是研究圆完美图的结构的 极其重要的途径。而且越来越多的证据显示，极小非圆完美图的结构非常复杂 在这篇文章中，我们发现；满足一定条件的花是极小非圆完美的并且我们从k d 出发，构造了多种类型的极小非圆完美图，其中一种构造方案是删去k ! 的一条 4 边，但这样的操作得满足一定的条件才可行，文中给出了相应的结果最后，我们 猜测g = k e ( 其中e k ) 不是极小非圆完美图只有两种情况z 要么 “屯( g ) = ) ( 。( g ) ，要么日含有导出真子图日是非圆完美的，并且日是我们 已经发现的通过删去鲍的一条边得到的一些极小非圆完美图 关键字：圆染色，圆色数，圆团数，圆完美图，极小非圆完美图 4 p r e f a c e t h ec o l o r i n gp r o b l e ma n dt h ec a l c u l a t i o no fc h r o m a t i cn u m b e ro f ag r a p ha r eo l dp r o b l e m sa t t r a c t i n gm u c ha t t e n t i o n a n dn o wt h e r e a r ev e r t e x - c o l o r i n g ，e d g e - c o l o r i n g ，f a c e - c o l o r i n g ，t o t a l l y = c o l o r i n g ，l i s t - c o l o r i n g ，c i r c u l a r c o l o r i n ga n ds oo n i nc o n v e n i e n c e ，v e r t e x - c o l o r i n g i ss h o r ta 8c o l o r i n g i nt h i st e x t ，w eo n l ys t u d yc o l o r i n ga n dc i r c u l a r - c o l o r i n g s i n c em y c i e l s k id i s c o v e r e dt r i a n g l e - f r e eg r 印h 8w i t ha r b i - t r a r i l yl a r g ec h r o m a t i cn u m b e r s ，w eh a v ek n o w n t h a tt h e r ei sl i t t l e r e l a t i o n s h i pb e t w e e nt h ec h r o m a t i cn u m b e ra n dt h ec l i q u en u m b e r b u ti fag r a p ha n de a c ho fi t si n d u c e ds u b g r a p h sh a v et h ep r o p e r t y t h a tt h ec h r o m a t i cn u m b e re q u a l st h ec l i q u en u m b e r ，t h e nt h eg r a p h i sc a l l e dp e r f e c t ，i n t r o d u c e db yc b e r g ei n1 9 6 0 ，h a st u r n e do u tt o b eo n eo ft h em o s tr e w a r d i n gi ng r a p ht h e o r y i no r d e rt os t u d y t h es t r u c t u r eo fp e r f e c tg r a p h ，m i n i m a l l yi m p e r f e c tg r a p h sa r ei n - t r o d u c e d f u r t h e r m o r e ，t h es t r o n gp e r f e c tg r a p hc o n j e c t u r ec a nb e r e f o r m u l a t e da sf o l l o w s ：t h eo n l ym i n i m a l l yi m p e r f e c tg r a p h sa r et h e o d dh o l e sa n dt h e i rc o m p l e m e n t s t h ec o n j e c t u r er e m a i n 8ab e a u t i - f u l ，s i m p l yf o r m u l a t e d ，b u tv e r yd i f f i c u l tp r o b l e m f o r t u n a t e l y , t h i s c o n j e c t u r eh a sb e e np r o v e dr e c e n t l ya sac o n s e q u e n c eo fr e s u l t sb y c h u d n o v s k y , r o b e r t s o n ，s e y m o u ra n dt h o m a s l 6 1 t h ec i r c u l a rc h r o m a t i cn u m b e ri sag e n e r a l i z a t i o no fc h r o m a t i c n u m b e r ，f i r s t l yi n t r o d u c e db yv i n c ef 3 】3 n a m e da ss t a rc h r o m a t i cn n m b e ri n1 9 8 8 a n di nr e c e n t1 0y e a r s ，t h i sc o n c e p th a sb e e nd e e p l y s t u d i e da n dr e c e i v e dm u c hd e v e l o pi n 【5 ，9 ，1 0 ，1 6 ，2 1 ，2 2 ，2 4 - 2 8e t c 】 5 a n a l o g o u st ot h ec o n c e p to fc l i q u en u m b e ra n dp e r f e c tg r a p h ，z h u 【1 7 i n t r o d u c e dt h ec o n c e p to fc i r c u l a rc 托q u en u m b e ra n dc i r c u l a r - p e r f e c tg r a p h h ea l s og a v es u f f i c i e n tc o n d i t i o n sa n dn e c e s s a r yc o n d i t i o l mf o rag r a p ht ob ec i r c u l a rp e r f e c t s i m i l a r l y , m i n i m a l l yc i r c u l a r - i m p e r f e c tg r a p hi sa l s ou s e dt os t u d yt h es t r u c t u r eo fc i r c u l a r - p e r f e c t g r a p h an a t u r a lq u e s t i o no n em a y a s ki sw h a ts t r u c t u r a lp r o p e r - t i e so fm i n i m a l l yc i r c u l a r i m p e r f e c tg r a p h 8a d m i t i ts e e i d _ st h a tt h e s t r u c t u r eo fm i n i m a l l yc i r c u l a r - i m p e r f e c tg r a p h si sm u c hm o r ec o m - p l i c a t e dt h a nt h a to fm i n i m a l l yi m p e r f e c tg r a p h s s i n c ek p l a c e s t h es a m er o l ei nc i r c u l a r - c o l o r i n ga 8 p l a c e si nc o l o r i n g ，w ec o n - s t r u c ts o m ef a m i l i e so fm i n i m a l l yc i r c u l a r i m p e r f e c tg r a p h sf r o mk i nc h a p t e r2 a n di nc h a p t e r1 ，w eg i v es o m ed e f i n i t i o n sa n dk n o w n r e s u l t s 6 c h a p t e r1 p e r f e c tg r a p h sa n d c i r c u l a r - p e r f e c t graphscircular-ertect r a d l 2 s 1 1d e f i n i t i o n sa n ds i g n s i nt h i sa r t i c l e ，g r a p h sc o n s i d e r e da r ea l lf i n i t ea n ds i m p l e u n d e f i n e d c o n c e p t sa n dt e r m i n o l o g i e sf o l l o w s 【4 】 l e tg = ( v ，e ) b eag r a p h ，w h e r eva n ded e n o t et h es e t o fv e r t i c e sa n de d g e so fg r e s p e c t i v e l y t w ov e r t i c e s “a n dt ，a r e a d j a c e n t ，d e n o t e db y 伽e ( g ) ，i ft h e r ei sa ne d g ei ne ( g ) j o i n i n g t h e m as i m p l eg r a p hi nw h i c he a c hp a i ro fd i s t i n c tv e r t i c e si sj o i n e d b ya ne d g ei st a i l e dac o m p l e t eg r a p h ac o m p l e t eg r a p hw i t hn v e r t i c e si sd e n o t e db y i f i sav e r t e xi ng t h e nn c ( v ) d e n o t e s t h es e to fv e r t i c e st h a ta r ea d j a c e n tt o 口i ng i n o ( v ) id e n o t e st h e n u m b e ro fe l e m e n t si n b ( 口) l e tg 。b et h ec o m p l e m e n tg r a p ho fg ， w h e r ev ( a 。) = v ( c ) a n de ( g 。) = u 口i ua n dua r en o n a d j a c e n ti n g ) ap r o p e rs u b g r a p ho fg i sas u b g r a p hw h i c hi sn o tt h eg r a p hg i t s e l f s u p p o s et h a tv 。i san o n e m p t ys u b s e to fv ，t h e nt h es u b g r a p h o fgw h o s ev e r t e xs e ti sv 7a n dw h o s ee d g es e ti st h es e to ft h o s ee d g e s o fgt h a th a v eb o t he n d si nv i sc a l l e dt h es u b g r a p ho fgi n d u c e db y a n di sd e n o t e db ya v 。】；w es a yt h a ta y 。】i sa ni n d u c e ds u b g r a p h o fg t h ec l i q u en u m b e ro fag r a p hg ，d e n o t e db yu ( g ) ，i st h e 7 m a x i m u mo r d e ro fac o m p l e t es u b g r a p ho fg as e tso fv e r t i c e s i sc a l l e da ni n d e p e n d e n ts e ti ft h es u b g r a p hi n d u c e db ys c o n t a i n s n oe d g e s t h em a x i m u mo r d e ro fi n d e p e n d e n ts e ti ngi sc a l l e dt h e i n d e p e n d e n tn u m b e r , d e n o t e db y 口( g ) as e tso fv e r t i c e si sd e l e t e df r o mag r a p hgi fs t o g e t h e rw i t h a 1 1t h ee d g e sw i t ha tl e a s to n ee n di ns i sr e m o v e df r o mg a n dt h e r e s u l t i n gg r a p hi sd e n o t e db ya s f o rg i v e ng r a p h sga n dh ，ah o m o m o r p h i s mf r o mgt ohi s am a p p i n g ，f r o mv ( a ) t ov ( h ) w h i c hp r e s e r v e st h ea d j a c e n tr e - l a t i o n s ，i e ，( 乱) ，( u ) e ( h ) w h e n e v e r 乱口e ( g ) i nw o r d so f h o m o m o r p h i s m ，t h ec l i q u en u m b e ro fgi st h em a x i m u mi n t e g e rz s u c ht h a t 硒a d m i t sah o m o m o r p h i s mt og l e tg = ( v ，e ) b eag r a p hw i t hv e r t i c e ss e t v ( a ) a n de d g e s s e te ( g ) ac h a i ni ngi saf i n i t en o n n u l ls e q u e n c ew = v o v l w h o s et e r m sa r ea l t e r n a t e l yv e r t i c e sa n de d g e ss u c ht h a tv i v i + 1 e ( g ) f o ri = 0 ，1 ，s 一1 ，i fw = v o v l a n dw = + 1 狮 a r ec h a i n s ，t h ec h a i n o o v l v l ，o b t a i n e db yc o n c a t e n a t i n gw a n d a tv s ，i sd e n o t e db yw w 。t h e l e n g t ho ft h ec h a i nw = v o v l 据 t h en u m b e ro fe d g e st h a tt h ec h a i np a s s e st h r o u g h ，d e n o t e d b yz ( 彬) ap a t hi sac h a i nw i t hd i s t i n c tv e r t i c e s ac y c l ei sap a t hw i t ht h e s a m eo r i g i na n dt e r m i n u s ap a t ho fl e n g t h 竹i sc a l l e da l ln - p a t h t h e g i r t ho fg i st h el e n g t ho ft h es h o r t e s tc y c l ei ng l e tc = 如口1 一l v ob eac y c l e g i v i n gca no r i e n t a t i o n w eo b t a i nad i r e c t e d - c y c l e ，d e n o t e db yc a n ds e tpb et h ec y c l e w i t ht h eo p p o s i t eo r i e n t a t i o no fc i fe = 蜘 1 一l v o ，t h e n g = v o v n 一1 u l t 协ap a t hp = 讧功+ 1 i ne ，i sd e n o t e db y v c o r 吻e 饥m e ni 歹，v _ f c v ji sd i f f e r e n tf r o mq 刁地，b u t 饥c v ja n dv j g 叻a r et h es a m e 8 1 2p e r f e c tg r a p h sa n dk n o w nr e s u l t s a nn c o l o 巧n go fgi sah o m o m o r p h i s mf r o mgt o t h e1 e a s t i n t e g e r 礼s u c ht h a tg a d m i t sa nn - c o l o r i n gi sc a l l e dt h ec h r o m a t i c n u m b e r o fg ，d e n o t e db y ) ( ( g ) c l e a r l y , gc o n t a i n sas u b g r a p h j 乙( g ， a n dh e n c ex ( g ) x ( k 。c c ) ) = u ( g ) a g r a p hg i sp e r f e c ti fga n de a c ho fi t si n d u c e ds u b g r a p h sh a v e t h es a m ec h r o m a t i cn u m b e r ) ( a si t sc l i q u en u m b e ru ，o t h e r w i s egi s c a l l e di m p e r f e c t am i n i m a l l yi m p e r f e c tg r a p hi sai m p e r f e c tg r a p h o fw h i c he a c hp r o p e ri n d u c e ds u b g r a p hi sp e r f e c t a no d dh o l ei n ag r a p hi sa ni n d u c e ds u b g r a p ht h a ti si s o m o r p h i ct oa no d dc y c l e o fl e n g t ha tl e a s tf i v e a n dt h e r ea r es o m es u f f i c i e n to rn e c e s s a r y c o n d i t i o n sf o rag r a p ht ob ep e r f e c t t h e o r e m1 1 川( t h ep e r f e c tg r a p ht h e o r e m ) t h ec o m p l e m e n to la p e r f e c tg r a p hi sp e r f e c t t h e o r e m1 2 7 1ag r a p hgi sp e r f e c t 谑a n do n l yi fe v e r yi n d u c e d s u b g r a p hgo fgs a t i s f i e st h ei n e q u a l i t y a ( ) u ( d ) i v ( g ) i af u r t h e rp o s s i b l ec h a r a c t e r i z a t i o no fp e r f e c tg r a p h si so n eo ft h e o u t s t a n d i n gp r o b l e m si ng r a p ht h e o r y , p o s e db yb e r g ei n1 9 6 0 ： t h es t r o n gp e r f e c tg r a p hc o n j e c t u r e ag r a p hg 妇p e r f e c t 矿 a n do n l y ，n e i t h e rgn o rc o m p l e m e n tg 。c o n t a i n sa no d dc y c l eo f l e n g t hg r e a t e rt h a t3a sa ni n d u c e ds u b g r a p h ， ， t h ea t t e m p t so fp r o v i n gt h i sc o n j e c t u r ef a l li n t ot w oc l a s s e s ：o n e d i r e c t i o ni st os t u d yt h es t r u c t u r eo fm i n i m a l l yi m p e r f e c tg r a p h s ；t h e o t h e ri st op r o v et h ec o n j e c t u r eu n d e rs o m ea d d i t i o n a lh y p o t h e s e s f o r t u n a t e l y , t h ec o n j e c t u r eh a sb e e np r o v e dr e c e n t l ya 8ac o n s e q u e n c e o fr e s u l t sb yc h u d n o v s k y , r o b e r t s o n ，s e y m o u ra n dt h o m a s 6 1 9 t h e o r e m1 3 ( t h es t r o n gp e r f e c tg r a p ht h e o r e m ) t h eo n l ym i n i m a l l yi m p e r f e c tg r a p h sa r et h eo d dh o l e sa n dt h e i rc o m p l e m e n t s 1 3 c i r c u l a r - p e r f e c tg r a p h sa n dk n o w nr e s u l t s t h ec i r c u l a rc h r o m a t i cn u m b e r ( o r i g i n a l l yc a l l e dt h es t a rc h r o m a t i c n u m b e rb yv i n c ei n 3 】) o fg r a p h si san a t u r a lg e n e r a l i z a t i o no ft h e c h r o m a t i cn u m b e ro fg r 印h s t h e r ea r eq u i t eaf e we q u i v a l e n td e f i n i t i o n so ft h ec i r c u l a rc h r o m a t i cn u m b e ro fg r a p h s s u p p o s er 2i sa r e a ln u m b e r l e tcb eac i r c l eo fe u c l i d e a nl e n g t hr a nr - c i r c u l a r c o l o r i n go fag r a p hg i sam a p p i n gcw h i c ha s s i g n st oe a c hv e r t e x 茁 o fga no p e nu n i tl e n g t ha r cc ( x ) o fc ，s u c ht h a tf o re v e r ye d g ex yo f g ，c ( x ) nc ( y ) = 0 t h e nt h ec i r c u l a rc h r o m a t i cn u m b e r i sd e f i n e d a s ： x c ( g ) = 锄， r ：ga d m i t sa nr - c i r c u l a rc o l o r i n g ) 、 。 f o l l o w i n gi sa ne q u i v a l e n td e f i n i t i o no fx c ( a ) f o rt w oi n t e g e r s 1 d k ，a ( k ，d ) 一c o l o r i n go fag r a p hgi sac o l o