（应用数学专业论文）一些图类的连续边着色.pdf

摘要 摘要 设g 是简单图，用颜色1 ，2 ，3 对g 的边着色。如果每一顶点所 关联的边上着的颜色构成一个连续的整数集合，那么就称这个边 着色是连续的。图的连续边着色在日程安排理论上有重要应用， 它先由k u b a l e 在文献【9 中引入介绍并且被文献 4 ，6 ，7 ，9 的作者研 究。图g 的亏度d e f ( g ) 是最小数目的悬挂边，他们粘在g 上使它 可连续边着色。 广义0 一图，简记为，是一个包含m ( 2 m 3 ) ，b i p a r t i t e o u r e r p l a n a rg r a p h s 6 】2 - p r o c e s s o ra n d3 - p r o c e s s o rb i p a r t i t eg r a p h s 1 0 ，b i p a r t i t ec a t c i 7 】a sw e l la sb i p a r t i t e ( 2 ，z x ) 一r e g u l a rg r a p h s 8 i np a r t i c u l a r ，g i a r o 1 g i v e st h ed e f i c i e n c yo ft h e f o l l o w i n gg r a p h s ： o d dc y c l e s ，w h e e l s ，b r o k e nw h e e l s ，a n dc o m p l e t eg r a p h so fo d d o r d e r i ts e a m sv e r yd i f f i c u l tt oc h a r a c t e r i z et h e g r a p h st h a th a v e c e ca n dt h e r ei saf e wo fs u c hg r a p h sc h a r a c t e r i z e d d e f i n i t i o n2 4l e tgb eag r a p ho f o - d e f i c i e n t b yt h es p a ns f g ，c 1 o fc o l o r i n gcw em e a nt h en u m b e ro fc o l o r su s e di nt h ec e c b y s ( g ) ( s ( g ) ) w ed e n o t et h em i n i m u m ( m a x i m u m ) s p n na m o n g 出l c e co fg ，r e s p e c t i v e l y c l e a r l y ，f o ra n y0 - d e f i c i e n tg r a p hg a ( g ) s ( a ) s ( c ) ag e n e r a l i z e do - g r a p hi sag r a p h c o n s i s t i n go fm i n t e r n a ld i s j o i n t ( u ，u ) 一p a t h s ，w h e r e2 m o 。t h r o u g h o u tt h et h e s i s w ed e n o t e t h eg e n e r a l i z e d 臼一g r a p hb y ao - g r a p hi s a 0 。f o rm ：3 瑶= k 1 + n k 2 i sag r a p ht h a tc o n t a i n sn t r i a n g l e ss h a r i n ga c o m m o nv e r t e xw t h ef o l l o w i n ga r es o m ek n o w nr e s u l t sw h i c ha r er e l a t e dt oo u r r e s u l t s l e tcb eac e co fg b yc m i n a n d n zw ed e n o t et h e m i n i m u ma n dm a x i m u mc o l o ru s e di n c ，r e s p e c t i v e l y o b v i o u s l y , e v e r yi n t e g e rb e t w e e nc m i na n dc m o 。i sac o l o ro fs o m ee d g e l e t b a s i cd e f i n i t i o n sa n dr e s u l t s 9 v l v 2 ，v nb eas e q u e n c eo fv e r t i c e so fa n yp a t hj o i n i n ga ne d g ec o l - o r e dw i t hc m i na n da ne d g ec o l o r e da m z f r o mt h ec o n s e c u t i v e n e s s o fci tf o l l o w st h a tt h ed i f f e r e n c eo fc o l o r sa s s i g n e dt oa n yt w o e d g e s i n c i d e n tw i t hv v ( a ) i sa tm o s td ( g ) 一1 t h u s n s ( g ，c ) = c m 。一c 。讥+ 1 1 + ( d ( ) 一1 ) i = 1 i nt h i sw a yw eo b t a i nt w os i m p l eb o u n d so nt h em a x i m u m s p a n p r o p o s i t i o n2 5 f o ra n yg r a p hgo fo - d 咖c i e n t s ( c ) p ( p ) 1 + m a x ( d ( 嵋) p 6 p、 w h e r epi st h es e to fa l ls i m p l ep a t h so g p r o p o s i t i o n2 6f o ra n yg r a p hgo fo - d e f t c i e n t s ( a ) ( d i a m ( g ) + 1 ) ( 一1 ) + 1 ， ( 2 5 ) ( 2 6 ) w h e r ed i a m ( e ) i st h ed i a m e t e ro g t h eb o u n do fp r o p o s i t i o n2 6w a si m p r o v e di nt h ec a s eo fb i p a r t i t eg r a p h sb ya s r a t i a na n dk a m a l i a n 3 t h e yt o o ka d v a n t a g eo fs i m p l ef a c tt h a ti na n yo - d e f i c i e n tg r a p ht h e r ea r et w o v e r t i c e so fe d g e sw i t he m 抽a n dc m n zc o n n e c t e db yap a t ho fl e n g t h d i a m ( g ) 一1 t h u sb yi n e q u a l i t y2 6w eh a v e p r o p o s i t i o n2 7 f o ra n yb i p a r t i t eg r a p hg o fo - d e f t c i e n t s ( a ) d i a m ( g ) ( a 一1 ) + 1( 2 7 ) n o t et h a tt h eb o u n d ( 2 5 ) i st i g h tf o rt r e e sa n dt h eb o u n d ( 2 7 ) i st i g h tf o rg r a p h sk m l m r e c e n t l y ，g i a r o 1 g i v e st h en e wu p p e r b o u n d so ns ( a ) i nt e r m so f b a s i cd e f t n i t i o n sa n dr e s u l t s 1 0 p r o p o s i t i o n2 8 1 i f g r a p hg i s0 ，0 一d e f i c i e n tw i t h 3v e r t i c e s ， t h e n s ( c ) 2 u 一4 ( 2 8 ) p r o p o s i t i o n2 9 l e tg b eat r i a n g l e - f r e eg r a p h0 ，o - d e f i c i e n t t h e n s ( c ) 一1( 2 9 ) t h eb o u n do fgd e f ( g ) s e e m st ob ean e wg r a p hi n v a r i a n t g i a r o 1 g a v et h el o w e rb o u n d f o raf e ws p e c i a lf a m i l i e so fg r a p h s p r o p o s i t i o n2 1 0 【1 l e tgb eaa r e g u l a rg r a p hw i t ho d d n u m b e r o v e r t i c e s t h e n d e ，( g ) i a ( 2 1 0 ) c o n s e c u t i v ee d g e - c o l o r i n g 3t h ec e co fg e n e r a lg r a p h s 1 1 i nt h i ss e c t i o nw eg i v et h ed e f i c i e n c i e so f ，露a n ds o i t i eo t h e r s p e c i a lg r a p h s l e t 晶= v o v l v nb ea ( v o ，v n ) 一p a t ho fl e n g t hna n dr i sc a l l e d o d di fni so d da n de v e n ，o t h e r w i s e t h ev e r t i c e s v 0a n dv n a r e c a l l e dt h eo r i g i na n dt e r m i n u so fp n i ti sw e l lk n o w na n de a s yt o s e et h a ta n y p a t hr h a sac e c ri ss a i dt ob e ( i ，j ) 一c o n s e c u t i v e l y c o l o r a b l ei frh a sac e ces u c ht h a te ( v o v , ) = ia n de ( v n 一1 v n ) = j ( w e a l s os a yt h a trh a sa n ( i ，j ) 一c e c ) s i n c e 只i sa nu n d i r e c t e d a n ds y m m e t r yg r a p h i f 晶h a sa n ( i ，j ) 一c e c ，t h e np nh a sa l s oa ( j ，i ) 一c e c i nt h ef o l l o w i n gl e m m a s ，w ec o n s t r u c tt h e ( i ，j ) 一c e c f o rp a t h 只 l e m m a3 1l e tp 2 k + lb eo d dp a t h ，w h e r ek 0 p 2 + 1i s ( i ，歹) 一 c o n s e c u t i v e l yc o l o r a b l e 毡a n do n l y 电ia n djh a v et h es a m ep a r i t y a n di i j i 2 k p r o o f “牟= ”b yi n d u c t i o no nf i 一外 f i r s tw es u p p o s et h a ti i j i = o ( t h a ti s ，i = j ) ap r o p e re d g e c o l o r i n gci sd e s i g n e df o rp 2 k + 1w i t hc o l o r si a n di + 1a l t e r n a t e l y a sf o l l o w s ，e ( v o v l ) = i ，e ( v l v 2 ) = i + l ，c ( v 2 k l v 2 k ) = i + 1 ， e ( v 2 k v 2 k + 1 ) = i c l e a r l y ，ci sa n ( i ，i ) 一c e co fp 2 k + 1 s u p p o s e ，n o w ，t h a tt h el e m m ah o l d sf o ra l li i j i 3 ) 碟= k 1 + 亿尥 i sag r a p ht h a tc o n t a i n s 钆t r i a n g l e ss h a r i n g ac o m m o nv e r t e x 叫i n f o l l o w i n gr e s u l t ，w ed e t e r m i n et h ed e f i c i e n c yo f 焉 t h e o r e m3 1 0l e tn 1b ea 2i n t e g e r t h e n d e f ( 爵)_ 1 玎2 0 i f n i so d d 惦e u e 咒 p r o o f w ed i s t i n g u i s ht w oc a s e s c a s e1 ：a s s u m et h a tni se v e na n dl e tn = 2 k 珐c a nb ec o n s e c - u t i v e l yc o l o r e dw i t hc o l o r s1 ) 2 ，7 j4 七a te a c he d g e ac o l o r i n gcf o r w h i c hd e f ( 咳，c ) = 0i sg i v e ni nf i g 4 ( a ) ，w h e r ec ( w u 2 i 一1 ) = 4 i 一3 ， c ( w v 2 i 一1 ) = 4 i 一1 ，c ( t , 2 i l v 2 i 一1 ) = 4 i 一2 ，c ( w ? u 2 i ) = 4 i 一2 ， c ( w v 2 i ) = 4 i ，c ( q a 2 i v 2 i ) = 4 i 一1 ( i = 1 ，2 ，七) c a s e2 ：s u p p o s et h a t 礼= 2 k + 1 ，w ef i r s tp r o v