（运筹学与控制论专业论文）图的圆着色及p圆着色的若干结论.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 ， 是否存在具有高连通性的临界图使得它的圆色数接近它的色数? 在这篇论文，我 们继续s t e f f e n 和z h u 的讨论，弥补了他们讨论中的一处小的遗漏，从而完善 了他们的结论，即对于任意整数m 3 ，k 2 ，总存在m - 连通( m + 1 ) 一 临界图h ( m ，k ) 使得x c ( h ( m ，惫) ) m + 1 k 设p 是个非平凡的具有传递性的性质，h a r a r y 首次提出p 着色的概 念，也就是条件着色。同时这一概念也得到了广泛研究本论文，我们引入z l 圆 着色的定义令k 和d 为正整数，图g 的一个( p ，k ，d ) - 着色是一个从y ( g ) i + d - 1 到磊的映射，使得对任意整数l ，( u7 r 一0 ) ) g p ；同时给出等价定义 并有如下简单的结论t 1 设( ，x 1 ，? x k 一1 ) 为图g 的一个( p ，k ，d ) 一着色，其中正整数k 和 d 互素如果存在某个整数t ，使得五= 毋，那么x 。( g ：p ) f i 9 1 1 v a r i a t i o n so nt h e