圖的列表著色和雙圈覆蓋猜想.pdf

1、Y 3 0 1 2 9 7博士研兜生學(xué)位論文新疆太學(xué)論文題目( 中文) ：論文題目( 英文) ；研究生姓名；學(xué)科、專業(yè)：研究方向：導(dǎo)師姓名職稱；圖的列表著色和雙圈覆蓋猜想L i s t C o l o r i n g s a n d C y c l e D o u b l eC o v e r o f G r a p h s王國(guó)平應(yīng)用數(shù)學(xué)圖論及其應(yīng)用黃瓊湘教授論文答辯日期：2 ：D 0 6 年 月 日學(xué)位授予目期：2 0 0 6 年 月

2、 日A b s t r a c tT h e p a p e ri n t r o d u c i n g m y s o m e r e s e a r c h e dr e s u l t so nl i s tc o l o r i n g sa n dc y c l ed o u b l ec o v e rc o n j e c t u r e so fg r a p h sr e s p e c t i v e l yi s

3、 d i v i d e di n t o t w op a r t s ．T h ef i r s tp a r t c o m p r i s e sC h a p t e r sf r o mo n e t of o u r ．C h a p t e ro n e i s i n t e n d e d8 s af i r s ti n t r o d u c t i o n t ob a s i cc o n c e p t s

4、a n dt e r m i n a t i o n so f g r a p h s ，t o g e t h e rw i t h t h eb a c k g r o u n d o n l i s tc o l o r i n go fg r a p h s ．I nC h a p t e r t w o ) w e p r o v e t h a t t h e c a r t e s i a np r o d u c t g

5、 r a p h so fac y c l ea n d ap a t hs a t i s f yt h e l i s t e d g ec o l o r i n gc o n j e c t u r e ．I nC h a p t e rt h r e e ，w es t u d y t h ec h o o s a b i l i t yo fab i p a r t i t eg r a p hB a n do b t a

6、i n ( a )S u p p o s et h a tU ∈B i sao d d v e r t e xa n dt h a tf ：V ( B 1 _ N i s af u n c t i o ns u c ht h a t ，沁) = f 血筍] a n d ，扣) = r ％- 學(xué)l + 1f o r ”∈y ( B ) ＼“．T h e nB i s ，．c h o o s a b l e ；( b ) S u p p o

7、 s et h a tt h e r ea r ea t l e a s td s ( u ) 一lo d dv e r t i c e si n Ⅳj ( u )a n df ：y ( 口) 一N i s a f u n c t i o ns u c ht h a t ，( u ) = 1a n d ／( v ) = 『! ；掣] + 1f o ru ∈V ( B ) ＼u T h e nB i s f —c h o o s a b

8、l e ；( C ) S u p p o s et h a t “a n dW a r e t w on o n a d j a c e n tv e r t i c e si n B ，w h e r eu i s a no d d v e r t e x a n da l lv e r t i c e si n ⅣB ㈨)a r eo d d ，a n d ，：V ( B ) _ N i s af u n c t i o ns u

9、c ht h a t ，( Ⅲ) = l ，，( u ) = r - 一i - ia n d ／( v ) = 『蘭學(xué)] + l f o r “ ∈y ( B ) ＼{ 釷，山) T h e nB i s ／- c h o o s a b l e ．I nC h a p t e rf o u r ，w eg i v et h ec h o i c en u m b e r s o fs o n l ec o m p o s i t i

10、o n g r a p h so fc y c l eb ye m p t yg r a p h ．T h e s e c o n dp a r tc o n t a i n s o n l yC h a p t e rf i v e ．F i r s t ，w ei n t r o d u c e t h ec o n c e p t o ft h e c o l o rf a c t o rb yw h i c ha s u f f

11、 i c i e n ta n dn e c e s s a r yc o n d i t i o n ( + ) o nt h e e x i s t e n c eo ft h ec y c l ed o u b l e c o v e rf o rac u b i cg r a p h i so b t a i n e d ．S e c o n d ，a c c o r d i n g r , ot h el e n g t ho

12、 fc i r c u i ta n d 8 - f l o wt h e o r e m ，w ed i v i d eg r a p h s i n t ot w oc l a s s e sa n db yt h e c o n d i t i o n ( + ) p r o v et h a ts o m eo ft h e m h a v eC D C ，r e s p e c t i v e l y ．K e y w o r