（基础数学专业论文）关于图的可选择性与唯一列表可染图研究.pdf

摘要 本文研究列表染色的若干问题，包括图的色一可选择性和o h b a 猜 想、某些平面图的( k ，z ) 一可选择性和( ，f ) 一边一可选择性，以及图( 尤 其是完全多部图) 的唯一列表可染性 如果图g 满足g h ( g ) = x ( g ) ，则称g 是色一可选择的关于图的 色一可选择性，2 0 0 2 年o h b af 7 1 】给出猜想：如果图g 满足j y ( g ) j 2 x ( g ) + 1 ，则g 是色一可选择的容易发现o h b a 猜想成立当且仅当 其对完全多部图成立，但是对完全多部图o h b a 猜想被验证的情况只有 图编+ 2 2 + ( 一3 ) ，l 、蚝，2 + ( 一1 ) 和甄+ 3 ，2 。( 一) ，l m 本文证明。完全多部图 甄+ 2 ，3 ，孙佧一t 一2 ) 1 “( t = 2 ，3 ，4 ；t 十2 ) 是色一可选择图因此得到，对 图+ 2 ，3 2 + 佧一卜2 ) ，1 杆( 亡= 1 ，2 ，3 ，4 ；t + 2 ) 及其所有一色子图o h b a 猜想成立对独立数最大为3 的图，2 0 0 4 年o h b a 【7 2 】证明了o h b a 猜想 的一个较弱的形式；如果图g 满足i y ( g ) is 敏( 回，且g 的独立数最大 为3 ，则g 是色一可选择的在此我们证明：若r t + 1 且 r + t ， 则g h ( 蚝帆2 。( 一，一o ，l “) = x ( 地机2 。( k 一，一o ，m ) = 此结果表明t 在如上 o h b a 的论断中，条件i y ( g ) i 2 x ( g ) 可以换成i y ( g ) i 2 x ( g ) + 1 即 对每个独立数最大为3 的图及其所有x ( g ) 一色子图o h b a 猜想成立 图的( ，z ) 一可选择性问题是图的一可选择性问题的推广关于图 的( 七，z ) 一可选择性，1 9 7 9 年e r d 6 s 等人【2 6 j 提出了如下猜想：对任意整 数m 1 ，每一个( ，2 ) 一可选择的图g 也是( k m ，z m ) 一可选择的1 9 9 6 年n z a 和峨t f 9 4 】证明了这个猜想在南= 2 和f = 1 的情形是正确的， 但是对任意的( ，f ) 验证这个猜想的工作还相差甚远本文证明：对任 意整数m 1 ，每一个没有一圈托= 3 ，4 ，5 或6 ) 的平面图是( 4 m ，m ) 一 可选择的这一结果推广了分别由l a m 等人【6 5 】由w a n g 和l i hf 1 0 6 】、 由f j j a v 2 等人【2 8 】给出的如上图都是4 _ 可选择的结果另一方面，我 们还证明：如果一个平面图g 不包含t 一圈0 = 3 ，4 ，5 或6 ) 且( g ) 4 ， v 则对任意整数m l ，g 是( s m ，m ) 一边一可选择的，这里当t 3 ，4 ，5 ) ， 或t = 6 但( g ) 5 时，s = ( g ) + l ；当t = 6 且( g ) = 5 时，s = 7 除了( g ) = 4 以及t = 6 且( g ) = 5 的情况之外，该结果推广了分别 由w a n g 和l i h 【1 0 5 ，l ( j 6 、z h a n g 和、v u 【1 1 4 j 、王维凡【1 1 7 给出的不包 含t 一圈( 亡= 3 ，4 ，5 或6 ) 的平面图都是( ( g ) + 1 ) 一边一可选择的结果 此外，作为我们主要结果的推论得到：每一个没有4 _ 圈的平面图g 都 是( ( g ) + 1 ) 一边一可选择的该结果也改进了z h a n g 和w i 给出的结 果t 如果图g 是没有4 _ 圈的平面图，则g 是s 一边一可选择的，这里当 ( g ) 5 时，s = ( g ) + 1 ；当( g ) = 5 时，s = 7 如果图g 存在一个列表安排三，使得g 有唯一的个n 染色， 则称g 是唯一一列表可染的，简称g 是u 七l g 图1 9 9 9 年m a l l d i a n 和m a l l m o o d i a n 【6 7 l 特征化了【厂2 l e 图2 0 0 1 年g h e b l e h 和m 8 l l m o o d i a nf 3 2 】深入地研究了完全多部图的唯一列表可染性，尤其是唯一3 一列 表可染性，除去9 个完全多部图不能确定之外，他们特征化了c ，3 l d 完全多部图与此同时，针对这9 个被剔除的图。他们提出了如下开 放问题：查证图鲍。2 nr = 4 ，5 ，8 ，鲍，3 ，4 ，硒。4 ，4 ，甄+ 4 ，5 和1 + 5 ，4 不是u 3 l a 图2 0 0 4 年z h a 0 等人 1 1 5 】证明了图配，3 ，4 不是u 3 l g 图本文首先研究u 2 l a 图特征化定理证明的简化问题然后证明z 图 虬，2 ，r ，r = 4 ，5 ，8 ，蜀。4 ，4 ，蜀。4 ，5 和甄+ 5 ，4 都不是u 3 三e 图因此，唯 一3 一列表可染的完全多部图得到全面特征化 关键词：列表染色；n 可选择图；选择数；b 边一可选择图；边一选 择数；色一可选择图；o h b a 猜想；完全多部图；( ，f ) 一可选择图；( ， ) 一 边一可选择图；可平面图；唯一列表染色；唯一虹列表可染图；m ( 后) 性质 v 1 a b s t r a c t s e v e r mp r o b k m so nl i s tc o l o r i n g s ，i n c l u d i n gc h r o m a t i c c 1 1 0 0 s b i l i 七yo f g r a p h sa n do h b a sc o n j e c t u r e ，( 七，1 ) c h o o s a b i l i t ya d ( 七，f ) _ e d g e _ c h o o s a b i l i t y o fs o m ep l a n a rg r a p l l s ，a n du n i q u e1 i s tc o l o r a b i l i t yo fg r a p h s ，e s p e c i a l l yf o r c o m p l e t em u l t i p a r t i t eg r 印h s 】h a v eb e e ns t u d i e di nt h i st h 俗i 8 ag r 印hgi 8c a l l e dc h r o m a t i r 血o o s a b l ei fg ( g ) = x ( g ) f 0 rt h e c h 0 0 s a b i l i t yo fg r 印l l s ，i n2 0 0 2o h b a 【7 1 】c o n j e c t u r e dt h a te v e r yg r a p hg w i t h2 x ( g ) + 1o rf e w 凹v e r t i c e 8i sd l m m a t i c _ c h 0 0 s a b l e i ti se a s yt os e e t h a to h b a sc o n j e c t u r eh o l d si fa n do n l yi fi th o l d sf o rc o m p l e t e u l t i p a r t i t e g r a p h s b u tf o rc o m p l e 七em u l t i p a r t i t eg r a p h 8 ，t h e 肛8 p h sf o rw h i c ho b h a s c o n j e c t u r eh a s b e e nv e r m e da r en o 七h i n gm o r et h a n 2 ，2 t ( 七一3 ) ，1 ，蚝，2 。忙一1 ) a n d + 3 2 ( 奄一一1 ) ，mi nt h i st h e s i 8w es h o wt h a tg r a p h s 托+ 2 ，3 2 ( 七一一2 ) ，l “ 0 = 2 ，3 ，4 ；七t + 2 ) a r ec h r o m a t i c d 1 0 0 s 曲l e h e n c eo h b a sc o n j e c t u r e h 0 1 d 8f o r 。k + 2 ，3 2 + ( k 一一2 ) ，1 “0 = l ，2 ，3 ，4 ；七t + 2 ) a n da 1 1 七一c h r o m 8 七i c s u b g r a p h 8o ft h e m f 0 rt h eg r 印h sw j t hi i l d e p e n d e n c en u m b e ra tm o s tt h r e e ， 8 sa 、v e a k e rv e r s i o no fo h b a sc o n j e c t u r e ，o h b af 7 2 】p r o v e dt h a ti fgi 88 g r 印h w i t hi y ( g ) i 2 x ( g ) 蛆dt h ei n d 印e n d e n c en 脚曲e ro fg i 8a tm o s t 3 ，t h e ngi 8c h r o m a 土i c d l o o s a b l e h e r ew ep r o g ( 蚝+ r ，2 + 似一r t ) ，1 “) = x ( j 岛+ r ，2 。佧一r t ) 1 村) = 七，w h e r er t + la i l d 惫r 十t l i sr 船u l ti i n p u e s t h 8 ti nt h ea b a v ea s s e r t i o ng i v e nb yo h b a ，t h ec o n d i t i o ni y ( g ) l 2 x ( g ) c a nb er 印l a c e db yl y ( g ) is2 x ( g ) + 1 n a m e l y io h b a 8c o n j e c t u r eh o l d s f o re v e r yg r a p hgw i t hi n d e p e n d e n c en u m b e ra tm o s tt h r e e 龇l d 龃lx ( g ) 一 c h r o m a t i cs u b g r 印1 l so fg t h e ( ，f ) 一c l l o o s 8 b i l i t yi sam o r eg e n e r a ls e t t i n gf o rh h 0 0 s 8 b i l i t y f o r ( ，f ) - c h o o s a b i l i t y i n1 9 7 9e r d 6 8e t8 1 2 6 】r a i s e dt h ec o n j e c t u r et h a te v e r y ( 七，f ) c h 0 0 s a b l eg r 印hg i 8a l s o ( 七m ，f m ) c h o o s a b l e6 竹8 l l i n t e g e rm 1 i n 1 9 9 6r i - l l z aa dv 0 嘻 9 4 】s h o w e dt h ea b o v ec o n j e c t u r ei st r u ei f = 2a n d z = 1 t h eg e i l e r a lp r o o ff o ra l lp a i r s ( 七，z ) ，h a w e v e r ，s t i l ls e e r n st ob ef a o b e y o n dr e a c h i nt h i st h e s i sw ep r a v et h a te w r yp l a 缸g r 印hw i t h o u t _ c y c l e 0 = 3 ，4 ，5o r6 ) i s ( 4 m ，m ) 砌l o o s a b l ef o ra l l i n t e g e rm 21 ，g e n e r m i z i n gt h e r e s u l t st h a tt h ea b a v eg r 印h s 盯e4 w h 0 0 s a b l e8 h o w nb yl 唧e ta 1 【6 5 】b y w a n ga n dl i h 【1 06 ，毗l db yf j j a v e ta 1 【2 8 】，r e s p e c t i v e l y 0 nt h eo t h e r h a n d ，w e8 1 8 0p r a v et h a te v e r yp l a n 甜g r 印hg 耐t h o u tt c y c l e ( 亡= 3 ，4 ，5 o r6 ) 跗l dw i t h ( g ) 4i s ( s m ，m ) e d g 眦h 0 0 s a b l ef o r8 1 1 i n t e g e rm l ， v l l w h e r e8 = ( g ) + 1i ft 3 ，4 ，5 ) ，o rt=6b u t ( g ) 5 ；s = 7i f = 6a n d ( g ) = 5 t h e 8 er e s u l t sg e n e r a l i z et h er e s u l t st h a te v e r yp l a n a r g r 印hgw j t h o u t 一c y c l ep = 3 ，4 ，5o r6 ) j s ( ( g ) + 1 ) 呻d g e _ c h 0 0 s 8 b l eg i v e n b yw a 皿ga n dl i h 【1 ( ) j ，1 0 f j 】b yz h a n ga n dw l l 【l l 钏，a n db yw a n g 【1 1 7 ， r e 8 p e c t i v e l y e x c e p t f o r t h ec a s e ( g ) = 4 ，a n d t h ec a s e f = 6a n d ( g j = 5 m o r e o 怕r ，a sac o 璐e q u e n c eo fo u rm a i nr e s u l tw e0 1 ) t a i nt h a te v e r yp l a n a r g r 印hgw i t h o u t “y c l ei s ( ( g ) + 1 ) _ e d g e c h 0 0 s a b l e ，w h i c ha 1 8 0i m p r o v e s t h er e s u l tg i v e nb yz h 8 n ga n dw u ：e v e r yp l a n a rg r 印hgw i t h o u th y c l e s i ss 呻d g e - c h o o s a b l e ，w h e r es = ( g ) + li f ( g ) 5 ；s = 7i f ( g ) = 5 a g r 印hg i sc a l l e du n i q u e l y 卜u s tc o l o r a b l e ，o ru 七l ef o rs h o r t ，i fi ta d m i t sa 南一l i s t8 s 8 i g n m e n tls u c ht h a tgh a sa u n i q u el c o l o r i n g i n1 9 9 9m a h - d i a na n dm a h m 0 0 d i a n 【6 7 】c h a r a c t e r i z e dt h eu 2 l gg r 印h s i n2 0 0 lg h e b l e h a n dm a h f n o o d i a nf 3 2 le x c e l l s j v e l ys t u d t h eu n i q u e1 i s tc o 王0 r a b i l i t yf o rc o m p l e t ei i m l t i p a r t i t e 伊a p h s ，e 8 p e c i a l l yf o ru 3 l gc o m p k t em u l t i p a r t i t eg r 印h s t h e yc h a r 8 c t e r i z e dt h eu 3 l gg r 印h sf o ro o m p l e t em u l t i p a r t i t eg r a p h 8 c 印tf o rn i n e 盯印h 8 a tt h es a m et i i n e ，f o rt h en j n ee x e m p t e dg r 8 p h st h e y g i v ea no p e np r o b k m ：v e r 晦a j lt h eg r 印l l s 拖。2 ，rf o rr = 4 ，5 ，8 ，拖，3 ，4 ， 蜀。4 4 ，甄柑，5 ，a d 硒十5 ，4n o t 崩n g 矿3 三g i n2 0 0 4z h a o e td f h 5 】s h o 删 t h a tg r a p h 鲍3 4i sn o tu 3 l g i nt h i st h 船i 8 、张p r o v i d ea8 i m p kp r 0 0 ff o r t h et h e o r e mo fc h a r a c t e r i z i n gt h eu 2 l gg r a p h s a n dw es h o wt h a tm lt h e 日a p l l s 鲍2 ，f o rr = 4 ，5 ，8 ，k l + 4 ，4 ，k l 。4 ，5 ，a n d 凰。5 ，4 盯en o t u 3 l g a s ar e 8 u l t ，t h e 【，3 l gc o m p l e t ei n u l t i p 盯t i t e 口a p h 8a r ec o m p l e t e l yc l l a r a c t * i z e d k e yw o r d s ：l i s tc o l o r i n g s ；南一c h o o s a b l eg r a p h s ；c h o i c en u m b e “七一 e d g e - d l o o s a b l eg r 印l l s ；e d g “l o i c en u m b e r ；c h r o m a t i e _ c h o o s a b l eg r 印h s ； o h b a s n j e c t u r e ；c o m p l e t em u l t i p a r t i t eg r a p h s ；( 庇，f ) 弋h 0 0 s a b kg r 印h s ； ( 七，f ) 刊g e 础o o s a b l eg r 印h s ；p 1 8 n a r 鲫h s ；u n i q u el i s tc 0 1 0 r i n 9 8 iu n j q u e l y 知一l i s tc o l o r a b l eg r a p h s ；p r o p e r t ym ( 而) 插图目录 3 1 定理3 2 1 中图口及f ( u 。) ( i = 1 ，2 ，6 ) 的长度 3 2 定理3 47 中图日及口( e ) ( e e ( 日) ) 的长度 3 3 定理3 4 8 中图日及r ( e ) ( e e ( 日) ) 的长度 4 1 u 2 三e 图j ，4 e ) 及其唯一2 一列表染色+ 乱2 圈g 及其2 一列表安排l 4 3 g = 吖的生成子图，r 与s 具有不同的奇偶性 4 4 g = 镑。t 的生成子图，r 和s 都是奇数，r 3 ，s 1 4 5 g = 铭“的生成子图，r 与s 都是偶数，r 4 ，s 2 4 6 g 一呓2 ，t 的生成子图，t 3 4 7 日= 啦+ 2 ( 七 o ) 的生成子图 4 8 h = 口；，1 ，h 2 o ) 的生成子图 4 。9 日一日；。2 。t + 1 ( 七2 ) 的生成子图。 4 1 0 日= 锩1 女+ 2 o ) 的生成子图 4 1 1 h = 呓盔k + l ( 七2 ) 的生成子图 1 l l 眈 盯 仡 他 他 似 佰 粥 丌 丌 报送博士学位论文简况表 论文题目关_ 丁图的可选择性与唯一列表可染图研究 授予学位的 作者姓名申玉发 基础数学 学科、专业 作者单位河北师范大学 地址石家庄市裕华东路2 6 5 号 专业技术 导师姓名何文杰 教授 职务 导师单位河北师范大学 地址石家庄市裕华东路2 6 5 号 论文隶属学科分类号注l 0 1 5 7 ，5 论文关键词注2列表染色，色可选择图，( 毛，) - 可选择图，唯一t - 列表可染图 论文摘要：本文研究列表染色中图的可选择性和唯一列表可染图的若干问题。 如果图g 满足c a ( g ) = 粥，则称g 是色。可选择的关于图的色- 可选择性，2 0 0 2 年o h b a 给出 猜想：如果圈g 满足i v ( g ) i 翌川6 1 ) + l ，则g 是色- 可选择的本文证明：对图j 昏2 3 2 ( k - 1 2 ) 1 t ( 仁2 ，3 ，4 ； 硷t + 2 1 及其所有七- 色子图o h b a 猿想成立；对每个独立数最大为3 的圈g 及其所有叫g ) _ 色子图o h b a 猜想成立，该结果改进了o h b a 在2 0 0 4 年给出的一个结果 图的 0 可选择性问题是图的“可选择性问题的推广关于图的编2 ) - 可选择性，1 9 7 9 年e r d 6 s 等人提出了如下猜想：对任意整数聊三l ，每个髓可选择的图g 也是( b 托砌) - 可选择的本文证明： 对任意整数m 兰l ，每个没有卜圈( f = 3 ，4 ，5 或6 ) 的平面图g 是( 4 m ，所) - 可选择的；每个没有卜圈o = 3 ，4 ，5 或6 ) 且( g ) 4 的平面图g 是c ，m ) - 边可选择的，这里当f 3 ，4 ，5 ，或f = 6 但( g ) 5 时， s = ( g ) + 1 ：当辟6 且( g 产5 时，s = 7 如上结果推广了分别由l 锄、x u 和l i u 、由w h n g 和l i h 、 由殉a v 等人、由z h a i l g 和w u 、由王维凡先前给出的关于如上图是4 - 可选择的和( ( g ) + 1 ) 边可 选择的结果作为主要结果的推论得到：每个没有4 圈的平面图g 都是( ( g ) + 1 ) 边- 可选择的该 结果也改进了z h a n g 和w u 的先前结果 如果图g 存在一个b 列表安摊l 使得g 有唯一的一个工- 染色，则称g 是唯一知列表可染的，简 称g 是眦c 图1 9 9 9 年m a h d i a n 和m a l l m 0 0 d i a l l 特征化了u 扎c 图2 0 0 1 年g h e b i e h 和m a l l m o o d i a l l 深入研究了【口三c 完全多部图，除去9 个完全多部图不能确定之外，他们特征化了【昭比完全多部 图同时针对这9 个被剔除的图，他们提出了如下开放问题：查证局2 ，r = 4 ，5 ，8 ，局3 4 ，k 1 4 ， 局4 5 和置1 5 。4 不是们c 图2 0 0 4 年z h a o 等人证明了图硒j ，4 不是叩c 图本文首先研究咙c 图特征化定理证明的简化问题然后证明：娲。2 ，。一，5 ，8 ，k 1 | ，4 ，局4 5 和足。4 也都不是叩c 图因此，唯一3 列表可染的完全多部图得到全面特征化 1 移一图与唯一2 一列表染色图的特征化，应用数学与计算数学学报，2 论文在何时以 ( 2 0 0 5 ) ，7 3 - 7 8 何种方式发表 2 o np r o p e n ym ( 3 ) o f s o m ec o m p l e t em u i t i p a n i t eg m p h s ，彳鲫加加协乃聊埘，d ， ( 1 d m 6 炯口r o r 泌3 5 ( 2 0 0 6 ) ，2 l l 2 2 0 3 o nu n i q u e l yi i s tc o i o m b i ec o m p l e t e m u l t i p a n “eg m p h s ，s u b m i n e dt o 爿憎 c d m 6 加口幻砌，a c c e p t e d 4 c h r o m a t i cc h o o s a b i l i t y o f ac l a s s o f c o m p l e t c m u l t i p a r t i t e g r a p h s ，s u b m i n e d t o ，0 ， 如胁r e s e d 彤 五印哪打f o 一，a c c e p t e d 5 o nu n i q u e l y4 - l i s tc o l o r a b l ec o m p l e t em u l i i p a n i t eg r a 曲s ，s u b m i 他dt o 彳陌 6 加口f o r 肠，a c c e p t e d 6 唯一3 一列表可染图。，和髟l 饥，的若干性质，河北科技师范学院学报，4 ( 2 0 0 5 ) ，4 2 - 4 5 获得学位日期 报送日期备注 收藏单位：北京图书馆( 中国国家图档馆) 。执行部门：国内资料组。 注l ：一般应注明中国图j 伟资料分类法的类号。 注2 ：为了文献标引工作从论文中选取出来用以表示全文主题内容信息款目的单词或术语。每篇 论文选取3 5 个词作为关键词。为了国际交流，应标注与中文对应的英文关键词。 报送博士学位论文简况表( 英文) 论文题目 r e s e a r c ho nc h o o s a b i l i l yo f g r a p h s 柚du n i q u c l yl i s tc o i o r a b l eg r a p h s 授予学位的 作者姓名 s h e n y u f ap u r em a t h e m a t i c s 学科、专业 作者单位 h e b e in o r r n a lu n i v e r s i t y 地址 2 6 5y u h u ar o a d ，s 蜘i a z l u a n g 专业技术 导师姓名 h e 、 ，e n i i ep r o f e s s o r 职务 导师单位 h e b e in o m l a lu n i v e r s n y 地 址2 6 5y u h u ar o a d ，s h u i a z h u a n g 论文隶属学科分类号注1 0 1 5 7 5 l i s tc o l o r i n g s ，c h m m a t i c c h o o s a b l e g r a p h s ，( t 0 - c h o o s a b l eg r a p h s ， 论文关键词注2 u n i q u e l y 缸l i s tc o l o r a b l eg m p h s 论文摘要( 英文) ：s e v e m lp r o b l e m so ni i s tc o i o r i n g s ，i n c l u d i n gc h 0 0 s a b i i t yo f g m p i i s 锄du i l i q i i s t c o l o r a b i l i t yo f g r a p h s ，h a v eb e e ns t u d i e di nt h i st h e s i s a g r 印hg i sc a l l e dc h r o m a t i c - c h o o s a b l ei f 函( g ) = ) q g ) f o r t h ec h m m a t i c - c h o o s a b i l n yo f 脚h s ，i n 2 0 0 2o h b ac o n j e c t u r e dt h a te v e r yg r a p hg w i t h2 根( i 卜lo r 诧w e rv e r t i c e si sc h r o m a t i c c h o o s a b l e 1 nt 1 1 i s t h e s i sw es h o wt h a to h ba sc o n j e c t u r ei st r u ef o rg r a p h s 墨+ 2 ，3 ，2 蚪五) 1 t o = 2 ，3 ，4 ；砭什2 ) a n d “l 如c h m m a t i cs u b g r a p h so ft h e m m o r e o v e w ep r 0 v et h a to h b a sc o n j e c t u r eh 0 1 d sf o re v e r yg r a p hgw i t h i n d e p e n d e n c en u m b e ra tm o s tt h r e ea n da l l 州g ) c h r o m a t i cs u b g r a p h so fg ，w h i c hi m p r 0 v e sar e s u l t g i v e nb y o h b a i n2 0 0 4 t h e i ) - c h o o s a b i l i t yi sam o r eg c n e r a is e t c i n gf o r 知c h 0 0 s 曲i l 吼f o r 僻d - c h 0 0 s a b i l i 饥i n1 9 7 9e r d d s e ta i m i s e dt 1 1 ec o n j e c t u r et h a te v e r y 以i ! ) 一c h o o s 曲l eg r a p hgi sa l s o ( 向 ，砌) - c h o o s a b l ef o ra l i i 1 i n t 1 1 i st h e s i sw ep m v et l a te v e r yp l 粕a rg r a p hgw i t h o u tf _ c y c l e ( 卢3 ，4 ，5o r6 ) i s ( 4 删，m h o o s a b l ef o ra n m 三1 ；a n de v e r yp l a n a rg m p hw 弛o u tf - c y c l e ( 目，4 ，5o r6 ) 粕dw i t h ( g ) 4i so 肌，m ) - e d g e - c h 0 0 s 曲l e f o ra l l 崆l ，w h c r e 产+ li f f 3 ，4 ，5 ，o rr = 6b u t ( g ) 5 ；产7 i f 户6a i l d ( g p 5 t h 髂er e s u n s g e n e r a l 嘶t h er e s u l t sm a tt l ea b o v eg r a p hi s4 - c h o o s a b l ea n d ( ( g 汁1 ) - e d g e c h o o s 曲l eg i v e nb yl a m ， x ua 1 1 dl i u ，b y w a l l ga n d l i h ，b y f u a v 手e ta 1 ，b y z h a n ga 1 1 d w u ，b y w a n g ，r e s p e c t i v e l y m o r e 0 v e la sa c o n s e q u e n c eo fo u rm a i nr e s u i tw eo b t a i nt h a te v e i yp l a n a rg r 印hg w i t h o u t4 一c y c l ei s ( ( g ) + 1 ) - e d g e c h 0 0 s a b l e ，w h i c ha l s oi m p r o v e sar e s u l tg i v e nb yz h a n ga n dw u a g r a p hg i sc a n e d u n i q u e l y 七- l i s tc o l o m b l e ，o r 眦e cf o rs h o r t ，i fi ta d m 沤ab i i s t 踮s i g 啪e n t 上s u c h t h a tgh a sau n i q u e 工一c o i o r i n g i n1 9 9 9m a h d i a na n dm a h m o o d i a nc h a r a c t e r i z e dt h eu 2 上cg r a p h s i n 2 0 0lg h e b l e ha 1 1 dm a h m o o d i a ne x l e n s i v e l ys t u d i e dt h e 们三cc o m p l e t em u i t i p a r t i t eg r a p h s t h e y c h a r a c t e r i z e dt h ec ，3 上cg r a p h sf o rc o m p l e t em u l l i p a r t i t eg r a p h se x c e p tf o rn i n eg 阻p h s a tt h es 蛐et i m e ， f o rt h en i n ee x e m p t e dg r a p h st h e yg i v ea n0 p e np r o b l e m ：v e r i 母a l lt 1 1 eg r a p h sk 毫2 r 一，5 ，8 ，娲3 ， 凰4 4 ，娲4 ，锄d 局5 4n o tb e i n g 叩c i n2 0 0 4 z h a 0 e ta 1 p r o v e d t h a t g r 印h 局3 ，4 i sn o t 眦e c i l l t l i s t h e s i sw ep r o v i d eas i m p l ep r o o f f o rt h et h e o r c mo f c h a m c t e r i z i i l gt l l e 吼cg m p h s a n dw es h o wt h a ta u t h eg r a p h s 娲，2 。一，5 ，8 ，局4 ，4 ，曷4 5 卸d 蜀5 ，4a r ea l s on o t 叩们a sar e s u i lt h e 们cc o m p l e t e m u i t i p a n j l eg r 印h sa r ec o m p l e t e i yc h a r a c t c r i z e d 1 彩一图与唯一2 一列表染色图的特征化，应用数学与计算数学学报，2 ( 2 0 0 5 ) ，7 3 - 7 8 ， 2 o np r o p e r 哆 彳( 3 ) o f s o m ec o m p l e t e m u l l l p a n i t e g r a p h s ，一淞f r 口协i 口 j b l 堋口“) ， c o 聊6 加口f n 甜3 5 ( 2 0 0 6 ) 2 1l - 2 2 0 3 o nu n i q u e i yi i s tc o l o r a b i ec o m p l e t e m u l t i p a r c i t eg m p h s ，s u b m _ n e dt 0 彳坩 论文在何时以 凸蝴6 加口，d ，缸，a c c e p i e d 何种方式发表4 c h r o m 砒i cc h o o s a b i l i t yo f ac i a s so f c o m p l e t em u l t i p a n i l eg r a p h s ，s u b m i 她dt o ，0 ， 如腩m s 鲫比 上玩p 哪豇f 0 h ，a c c e p t e d 5 o nu n i q u e i y4 - l i s tc o l o r a b l ec o m p l e t em u i t i p a r t i t eg r a p h s ，s u b m i 仕e dt o 憎 c d 聊6 f 聆d f d r j o ，a c c e p t e d 6 唯一3 一列表可染图足。和足l ”的若干性质，河北科技师范学院学报，4 ( 2 0 0 5 ) ， 4 2 - 4 5 获得学位日期报送日期备注 收藏单位：北京图书馆( 中国国家图书馆) 。执行部门：国内资料组。 注1 ：一般应注明中国图书资料分类法的类号。 注2 ：为了文献标引工作从论文中选取出来用以表示全文主题内容信息款目的单词或术语。每篇 论文选取3 5 个词作为关键词。为了国际交流，应标注与中文对应的英文关键词。 第一章引言 1 1 综述 图染色问题是图论的一个重要研究领域，有着深刻而丰富的理论结果和广 泛的实际应用，其理论和方法在离散数学中占有重要地位众所周知，对经典的 图染色问题，尤其是对充满魅力的四色猜想的研究与图论学科本身的发展密不 可分尽管在1 9 7 7 年a p p e l 、h a k e n 和k o c h 【7 ，8 1 借助于计算机给出了四色猜 想的证明( 1 9 9 6 年，r o b e r t s o n 、s a n d e r s 、s e y m o u r 和t h o m a s 【7 9 ，8 0 】给出了四 色猜想的另一简单证明，但这个证明仍然是借助于计算机给出的) ，使四色猜想 成为四色定理，但这并没有影响人们对图染色问题的关注一方面，许多数学家 对他们借助计算机的证明不甚满意，希望能够找到四色猜想的直接理论证明；另 一方面，随着时代的发展，图染色问题的研究领域不断扩大，应用更加广泛，新 的理论和方法不断出现这一点可以从j e n s e n 和t o n 的著作g r 印hc o l o r j n g p r o b l e m s 5 f ) ( 1 9 9 5 年) 中看出在该著作中作者列举了来自实际问题和来自纯 数学研究的各种各样的图染色问题 由于涉及实际应用的图染色问题都必须满足一定的限制条件，这促使人们去 考虑并研究图的限制染色问题。图的限制染色是图的通常染色的变形和一般化， 包括列表染色、t 染色、预先染色的扩张等问题近二十年来大量的研究结果 涌现在图的限制染色领域 本文主要研究列表染色( l i s tc o l o r i n g s ) 的一些问题列表染色的概念最早 是由z i n gf 0 6 】( 1 9 7 6 年) ，由e r d 6 s 、r u b i n 和t 8 y l o rf 2 q ( 1 9 7 9 年) 独立地提 出来的所谓图的列表染色( 简称上一染色) 指的是，事先对图g 的各个顶点” 指定一个许可的颜色集合( 颜色表) l ( 钉) ，使得在对图g 的顶点进行染色时。各 个顶点的颜色必须从相应的颜色表中选取且保证染色是正常的如果图g 存在 】 博士学位论文第一章引言 一个p 染色，则称g 是l 一可染的 通常将图g 的颜色表l ( ) 的全体称为g 的一个列表安排，记为l 如果 在图g 的一个列表安排l 中每个颜色表中都恰好含有七个颜色，则称l 为g 的个一列表安排，其中叫做颜色表的长度如果图g 对它的任何一个 列表安排l 都是l 一可染的，则称g 是可选择的使图g 是七一可选择的最 小的正整数七称为g 的选择数( c h o i c en u t r l b e r ) ，记为g h ( g ) 或( g ) 如果一个列表安排l 是对图g 的边集e 给出的，平行地可得到g 的列表一 边一染色和七一边一可选择的及其相关概念，图g 的边一选择数( e d g e 弋h o i c e n u m b e r ) 记作g 7 ( g ) 或x ，