（運(yùn)籌學(xué)與控制論專業(yè)論文）圖的圓著色及p圓著色的若干結(jié)論.pdf

a b s t r a c t 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 ft h ec h r o m a t i cn u m b e r ， a n di tw a sf i r s ti n t r o d u c e db yv i n c ew i t ht h en a m et h es t a rc h r o m a t i cn u m b e r l e t 0b eap o s i t i v en u m b e r ，d o e st h e r ee x i s t sac r i t i c a lg r a p hg o fh i g hc o n n e c t i v i t y s u c ht h a tx o ( a ) x ( g ) 一1 + ? s t e f f e na n d z h ua n s w e r e dt h i sq u e s t i o na l m o s t c o m p l e t e l y , w h e r es o m em a r g i n a ls i t u a t i o n sa r el e f t i nt h i st h e s i s ，w ec o n t i n u e t h e i r r e s e a r c ha n dr e s o l v et h el e f tm a r l i n e s of a r ，w ea n s w e rt h eq u e s t i o nc o m p l e t e l y l e tpb eah e r e d i t a r ya n dn o n t r i v i a lp r o p e r t y , h a r a r yf i r s ti n t r o d u c e dt h e c o n c e p to fpc o l o r i n g ( c o n d i t i o n a lc o l o r i n g ) t h ec o n c e p tw a ss t u d i e de x t e n s i v e l y s i n c et h e n i nt h i st h e s i s w eg e n e r a l i z e dpc o l o r i n gt op c i r c u l a rc o l o r i n g ( 1 e t 七a n d db ep o s i t i v ei n t e g e r s ，a ( p ，鳧，d ) 一c 0 1 0 r i n go fg i saf u n c t i o ncf r o mv ( a ) t oz ks u c h t h a t ( u 霄一( 1 ) ) g p f o ra n yi n t e g e r 力，a n dt h e ng i v e8 0 m ee q u i v a l e n td e f i n i t i o n s o fi t i nt h ee n d ，w eg e ts o m es u f f i e n tc o n d i t i o n sa b o u tx c ( g ：p ) = x ( g ：p ) ，e g 1l e t ( x o ，x 1 ，拖一1 ) b ea ( p ，k ，d ) 一p a r t i t i o no fgw h e r eg c d ( k ，d ) = i i f 五= o f o rs o m e t ，t h e nx c ( g ：p ) 0 ， 是否存在具有高連通性的臨界圖使得它的圓色數(shù)接近它的色數(shù)? 在這篇論文，我 們繼續(xù)s t e f f e n 和z h u 的討論，彌補(bǔ)了他們討論中的一處小的遺漏，從而完善 了他們的結(jié)論，即對(duì)于任意整數(shù)m 3 ，k 2 ，總存在m - 連通( m + 1 ) 一 臨界圖h ( m ，k ) 使得x c ( h ( m ，憊) ) m + 1 k 設(shè)p 是個(gè)非平凡的具有傳遞性的性質(zhì)，h a r a r y 首次提出p 著色的概 念，也就是條件著色。同時(shí)這一概念也得到了廣泛研究本論文，我們引入z l 圓 著色的定義令k 和d 為正整數(shù)，圖g 的一個(gè)( p ，k ，d ) - 著色是一個(gè)從y ( g ) i + d - 1 到磊的映射，使得對(duì)任意整數(shù)l ，( u7 r 一0 ) ) g p ；同時(shí)給出等價(jià)定義 并有如下簡單的結(jié)論t 1 設(shè)( ，x 1 ，? x k 一1 ) 為圖g 的一個(gè)( p ，k ，d ) 一著色，其中正整數(shù)k 和 d 互素如果存在某個(gè)整數(shù)t ，使得五= 毋，那么x 。( g ：p ) f i 9 1 1 v a r i a t i o n so nt h e