（运筹学与控制论专业论文）图的l21标号问题及其推广.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：二蝉 日 期：j 坐学习 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅：本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：望q 丝丑：导师签名： 日期： 兰：堑塑? ，j 9 山东大学博士学位论文 图的l ( 2 ，1 ) 标号问题及其推广 邵振东 山东大学数学与系统科学学院 摘要 图的染色理论是图论中的一个重要研究课题，许多图论中的理论都是围绕 着它展开的。对它的研究可以追溯到百多年以前。图的染色理论既有着广泛 的实际应用背景，又是极有趣味的数学课题。 本文中所述的图的r 染色与图的( 2 1 ) 标号问题是从不同角度对圈的染色 问题的推广。 图的z ( 2 ，1 ) 标号问题作为图的染色问题的推广既有强烈的应用背景，又有 着较大的理论探讨价值。图的l ( 2 ，1 ) 标号问题的研究背景是频率分配问题。频 率分配问题最早是1 9 8 0 年由h a l e 在文献【6 】中提出的。h a l e 给出的定义是这样 的：给定一些无线电发射台，我们要求对每个无线电发射台分配一个频率使得 相互干扰的无线电发射台所分配的频率的间隔在允许的范围之内。h a l e 6 将此 问题归结成图的丁? 染色问题，丁染色问题在过去的十年里被广泛地加以研究f 见 【3 4 ，7 ，2 2 ) 。【2 中指出r o b e r t s 提出了在几个不同地点的无线电发射台有效地分 配无线电频率，频率用非负整数表示，使得相近的地点分配到不同的频率，相 邻的地点分配的频率至少相差2 ，从而使得这些频率不会相互干扰。g e r a r d j c h a n g 和d a v i dk u o 于1 9 9 6 年在【2 中更精确地提出图g 的个l ( 2 ，1 ) 标号是 一个从顶点集矿( g ) 到非负整数集的函数f ( x ) ，使得若d ( x ，y ) = l ，则 1 f ( x ) 一f ( y ) i 2 ；若d ( x ，y ) = 2 ，则i f ( x ) 一f ( y ) l 1 。图的一个k l ( 2 ，1 ) 标号是 图的一个z ( 2 ，1 ) 标号，使得所有标号都小于等于k 并且至少有一个达到k 。图g 的( 2 ，1 ) 标号数，用a ( g ) 表示，是一个使得g 有一个k l ( 2 ，1 ) ，标号的最小数 k 。 g r i g g s 和y e h 5 于1 9 9 2 年给出了路只，圈c 。和轮图既的l ( 2 ，1 ) 标号数 丑( 只) ，a ( c 。) ， ( ) 的精确值。j o n a s 3 6 】于1 9 9 3 年证明了对疗一方体q ，有 n + 3 旯( q 。) 。g r i g g s 和y e h 5 于1 9 9 2 年证明了当, 5 时，有a ( 幺) 2 n + 1 ， 并给出了当n 5 时兄( q ) 的精确值。w h i t t l e s e y ( 3 e o r g e s 和m a u r o 2 3 】于1 9 9 5 年证明了五( q 。) 2 + 2 “口“一2 ，这里h 2 一q 且1 s q s k 十l 。特别地。 置( q n 。) 2 。一i 。作为一个推论，对n 3 ，有五( g ) 2 n 。对最大度为l 的 树t ，g r i g g s 和y e h 5 】证明了五( r ) 为+ 1 或+ 2 。他们还证明了对一般图 的z ( 2 ，1 ) 标号问题是n p 完备闯题。g e o r g e s ，m a u r o 和w h i t t l e s e y 1 0 】1 9 9 4 年 研究了图的z ( 2 ，1 ) 标号数与其它图参数及图g 的路覆盖数的关系，并证明了： = ：= ：= ：= ：! 些查i ：耋矍圭兰篁墼兰 ( 1 ) 5 且仅当c ( g ) = 1 时，有a ( g ) 盯一l 。( 2 ) 令，为一个整数且，2 ，则有当且仅 当c ( g ) = r 时，有丑( g ) = n + r 一2 。对最大度为的一般图g ，g r i g g s 和y e h 5 】 证明了五( g ) sa 2 + 2 。当g 是3 一连通时，上界被改进为五( g ) a 2 + 2 一3 ：当 g 的直径为2 时，有五( g ) 2 。g r i g g s 和y e h 5 还提出猜想：对最大度为 的一般图g ，有丑f g ) ! 2 。 g e r a r dj c h a n g 和d a v i dk u o 2 于1 9 9 6 年证明了对最大度为的一般图 g ，有a ( g ) 2 + a ，但离该猜想还有一定的距离。要直接证明该猜想是困难 的，因此人们转而研究某类图的l ( 2 ，1 ) 标号数的上界，证明它们的l ( 2 ，1 ) 标号 数的上界符和上述猜想。为更精确地刻画这一问题，g e r a r dj c h a n g ，w ik e ，d k u o ，d d 一el i u 和r k y e hf 3 7 于2 0 0 0 年将图的z ( 2 ，1 ，标号问题推广到图 的l ( d ，1 ) 一标号问题，并证明了对最大度为的一般图g ，有 九( g ) , x 2 + ( d 一1 ) a 。他们还得出树等几类图的l ( a ，1 ) 标号的上界。 本论文的所有的结果主要是围绕图的l ( 2 ，1 ) 一标号问题的g f i g g s 和y e h 的猜 想而进行的，部分地证明了此猜想是成立的，同时还将图的l ( 2 ，1 ) 标号问题做 了不同的推广。 本论文的内容可分为以下五个部分： l 、第一部分证明了所研究的几类图的l ( 2 ，1 ) - 标号数的上界符和上述猜想。 其主要结果如下： 定理2 2 9 对最大度为的一般简单平面图g ，有a ( g ) 1 0 4 。 定理2 3 5 对最大度为的一般细分图瓯( g ) ( ”3 ) ，有五( s 。( g ) ) 2 a 。 定理2 4 1 对最大度为的任无世。铆3 ) 简单图g ，有 五( g ) s ( 譬) a 2 + 2 4 。 f 一l 定理2 4 2 r 单位球图g r ( r 2 2 ) 为无足。、图，对最大度为的r 一单 位球图g 月( r 2 ) ，有丑( g r ) ( 黼) 2 + 2 a 。 定理2 5 1 对最大度为的全图t ( g 1 ，有 三2 + 三 42 三2 + 2 当6 时 当 6 时 定理2 6 1 对般简单块图g ，若g 的每一个块的顶点数至少为3 ，则有 a ( g 1 2 。 定理2 7 2 对于两个图g 和日的笛卡儿乘积图g h ，设g x h 的最大度 为a ，g 的最大度为a ( g ) ，h 的最大度为( 日) ，则有x ( g h ) s 2 ( 例外为 a ( g ) 和( j v ) 至少一个为一，此时a ( g ) a 2 + 1 ) 。 定理2 8 1 对两个图g 和日的复合图g i n 】，设a n 】的最大度为，g 的最大度为( g ) ，h 的最大度为a ( h ) 。若“g ) 1 ，则有丑( g 厅】) 2 一l 。 定理2 9 1 对最大度为的g # l e s e r 图，当a 一2 b b 时，五( g ) 兰岔；当 ll 0 口一2 b b 时，x ( g ) ( 等) ”2 6 岔+ 2 4 ，其中0 ( 等) “2 6 1 ；当 山东大学博士学位论文 a 一2 b = 0 时，兄( g ) = 2 ；当一b a 一2 b 0 时，2 ( g ) = 0 。 定理2 1 0 1 对最大度为a 的高度不正则图g ，有a ( g ) 兰三二兰。 定理2 1 1 1 对图g 的m y c i e l s k i 图p ( g ) ，若其最大度为( ( g ) ) ，则有 五( ( g ) ) 量3 ( ( g ) ) 。 定理2 1 2 1 对图g 的d e s c a r t e s 图h ，有2 ( h ) 考；( ( 胃) ) 2 ，其中 o 若“ 定理2 1 3 1 对最大度为的h a l i n 图g ，有 ( g ) s3 a + 9 。 2 第二部分研究了关于几类平面图及相关图的三似，1 ) 一标号问题、图的2 一色 数z 2 ( g ) 与图的l ( d ，1 ) 一标号问题、细分图只( g ) 的l ( d ，1 ) 一标号数的上界、r 一 单位球图的g ( d ，1 ) 一标号数的上界、全图的l ( d ，1 ) 一标号数的上界、块图t ( g ) 的 l ( d ，1 ) 一标号数的上界、乘积图的三( d ，1 ) 一标号数的上界、复合图的l ( d ，1 ) 一标 号数的上界、k n e s e r 图的l ( d ，1 ) 一标号数的上界、高度不正则图的l ( d ，1 ) 一标号 数的上界、m y c i e l s k i 图的l ( d ，1 ) 一标号数的上界、d e s c a r t e s 图的l ( d ，1 ) 一标号 数的上界。 3 第三部分将图的l ( 2 ，1 ) 一标号问题推广到图的l ( d 。，d 2 ) 一标号问题，并研究了 第二部分所研究的几类图的l ( d 。，d ：) 一标号问题。 4 第四部分将图的上( 2 ，1 ) 一标号问题推广到更一般的情形即图的 l ( n ，n l ，1 ) 一标号问题。 5 第五部分将图的l ( 2 ，1 ) 标号问题推广到最一般的情形即图的 l c d ，d ”d 。) 一标号问题。 本论文的主要创新点如下： 1 g r i g g s 和y e h 提出猜想：最大度为的一般图g ，有五( g ) 2 。我们证 明了此猜想对几类平面图及相关图、细分图、r 一单位球图、全图、块图、乘积 图、复合图、k n e s e r 图、高度不正则图、m y c i e l s k i 图、d e s c a r t e s 图是成立的。 2 我们将图的l ( 2 ，1 ) 标号问题推广到图的l ( d l ，d 2 ) 一标号问题，并分别研究 了上述几类图的l ( d ，吐) 一标号问题，给出了它们的标号数的上界，作为推论， 也证明了g r i g g s 和y e h 的猜想对上述几类图是成立的。 3 我们还将图的三( 2 ，1 ) - 标号问题推广到图的l ( n ，h l ，1 ) 一标号问题和图 的工( 吐，d 。，以) 一标号问题。并证明了平面图的( 一，打一l ，1 ) 一标号和 l ( d 。，d 。，d 。) 一标号的上界可降至关于的n 一1 次多项式。 论文主题词：图，染色，丁一染色，l ( 2 ，1 ) 一标号，三( 九，以一l ，1 ) 一标号 上( 矾，如，以) 一标号 !： ! ：坐童奎兰塞圭兰堡竺兰= ：。：一! ： ：= ! = = ： t h el ( 2 ，1 ) 一l a b e l i n g s0 ng r a p h s a n di t sg e n e r a l i z a t i o n s s h a o z h e n d o n g m a t h e m a t i c sa n ds y s t e ms c i e n c ec o l l e g eo fs h a n d o n g u n i v e r s i t y a b s t r a c t t h e t h e o r yo fg r a p hc o l o r i n gi sav e r yi m p o r t a n tp r o b l e mt os t u d yi ng r a p ht h e o r y ， m a n y t h e o r i e si ng r a p h t h e o r y a r ed e v e l o p e da r o u n di t t h es t u d yo fi tc a l lb et r a c e dt o o v e ro n eh u n d r e d y e a r sa g o t h et h e o r yo fg r a p hc o l o r i n gh a s b r o a da c t u a la p p l i c a t i o n b a c k g r o u n da n d i sa l s oav e r yi n t e r e s t i n gm a t h e m a t i c a l p r o b l e m t h et - c o l o r i n ga n d l ( 2 ，1 ) 一l a b e l i n gp r o b l e mo ng r a p h si n t h i sp a p e ra r e b o t h g e n e r a l i z a t i o n so f t h ec o l o r i n gp r o b l e m s w i t hd i f f e r e n t p o i n t so f v i e w a sag e n e r a l i z a t i o no f c o l o r i n gp r o b l e m o n g r 印l l s ，t h el ( 2 ，1 ) 一l a b e l i n gp r o b l e m o n g r a p h sh a si n t e n s i v ea p p l i c a t i o nb a c k g r o u n da n d a l s o r e l a t i v e l yg r e a tt h e o r e t i c a l i n v e s t i g a t i n gv a l u e s t h es t u d yb a c k g r o u n do f t h el ( 2 ，1 ) 一l a b e l i n gp r o b l e m o n g r a p h s w a st h ef r e q u e n c y a s s i g n m e n tp r o b l e mw h i c hw a sf i r s t l yp u tf o r w a r db yh a l ei n 【6 】i n 19 8 0 t h ed e f i n i t i o ng i v e n b y h a l ew a sa sf o l l o w s ：t h ef r e q u e n c ya s s i g n m e n t p r o b l e m i st oa s s i g naf r e q u e n c yt oe a c hr a d i ot r a n s m i t t e rs ot h a ti n t e r f e r i n gt r a n s m i t t e r sa r e a s s i g n e df r e q u e n c i e sw h o s es e p a r a t i o ni sn o ti nas e to f d i s a l l o w e ds e p a r a t i o n s h a l e 【6 f o r m u l a t e dt h i sp r o b l e mi n t ot h en o t i o no f t h et c o l o r i n go f ag r a p h ，a n dt h e t c o l o r i n gp r o b l e m h a sb e e n e x t e n s i v e l ys t u d i e do v e rt h ep a s td e c a d e ( s e e 3 , 4 ，7 ，2 2 】) i n 【2 】s h o wt h a tr o b e r t sp r o p o s e dav a r i a t i o no ft h ec h a n n e la s s i g n m e n tp r o b l e mi n w h i c h ”c l o s e ”t r a n s m i t t e r sm u s tr e c e i v ed i f f e r e n tc h a n n e l s a n d ”v e r y c l o s e ” t r a n s m i t t e r sm u s tr e c e i v ec h a n n e l st h a ta l ea tl e a s tt w oc h a n n e l sa p a r t t of o r m u l a t e t h ep r o b l e mi nag r a p h s ，t h et r a n s m i t t e r sa r er e p r e s e n t e db yt h ev e a i c e so fa g r a p h ； t w ov e t r t i c e sa r e ”v e r yc l o s e ”i f t h e ya r ea d j a c e n ta n d ”c l o s e ”i ft h e ya r eo fd i s t a n c e t w oi nt h eg r a p h g e r a r dj c h a n ga n dd a v i d k u o 【2 】p u t f o r w a r dm o r e p r e c i s e l yt h a t a n l ( 2 ，1 ) - l a b e l i n go f ag r a p hgi saf u n c t i o n f f r o mt h ev e r t e xs e t v ( g ) t ot h es e t o fa l l n o r m e g a t i v ei n t e g e r s s u c ht h a t i f ( x ) 一，( y ) l 2 i f d ( x ，y ) = 1 a n d lf ( x ) 一( y ) 陋1 i f d ( x ，j ，) = 2 ak l ( 2 ，1 ) - l a b e l i n gi sa nl ( 2 ，1 ) 一l a b e l i n gs u c ht h a t n ol a b e li sg r e a t e rt h a nk t h e l ( 2 ，1 ) 一l a b e l i n gn u m b e r o fg ，d e n o t e db y a ( g ) ，i s t h es m a l l e s tn u m b e rks u c ht h a tgh a sa k l ( 2 ，1 ) - l a b e l i n g g r i g g sa n dy e h 5 】i n 1 9 9 2d e t e r m i n e dt h ee x a c tv a l u e so f 五( 只) ( g ) ，a n d a ( ) ，w h e r e 只i s ap a t h o f 竹v e r t i c e s ，c n i sac y c l eo f 一v e r t i c e s ，a n d 陟：i sa n 一一w h e e lo b t a i n e df r o m eb ya d d i n gan e w v e r t e xa d j a c e n tt oa l lv e r t i c e si n c n f o r 一一c u b e 见，j o n a s 【3 6 】i n 1 9 9 3s h o w e dt h a t 疗+ 3 五( q ：) g r i g g sa n dy c h 5 】i n1 9 9 2s h o w e dt h a t 五( g 一) 2 n + lf o r 玎5 t h e ya l s od e t e r m i n e d 五( 幺) f o r 九5 w h i t t l e s e y , g e o r g e s a n d m a u r o 2 3 】i n 1 9 9 5 p r o v e dt h a t 五( g ) 2 。+ 2 。9 ”一2 ，w h e r e n 2 一口 a n d l s q s k 十i i n p a r t i c u l a r , 五( q 2 。一 一i ) 2 。一i a sa c o r o l l a r y , 些圣塑竺篓丝圣一 2 ( q 。) 9 2 nf o r ”3 f o r a t r e e tw i t h m a x i m u m d e g r e ea 1 ，g r i g g sa n d y j h 【5 】 s h o w e dt h a t a ( r ) i se i t h e r + 1o r + 2 t h e yp r o v e dt h a tt h el ( 2 ，1 ) 一l a b e l i n g p r o b l e mi sn p c o m p l e t ef o rg e n e r a lg r a p h s g e o r g e s ，m a u r oa n dw h i t t l e s e y 【10 i n l9 9 4s t u d i e dt h er e l a t i o n s h i p a m o n gt h el ( 2 ，1 ) - l a b e l i n g o ng r a p h s ，o t h e rg r a p h p a r a m e t e r sa n d t h ep a t hc o v e r i n g n u m b e r o fg 。t h e yp r o v e d t h a t ：( 1 ) z ( g ) n 一1 i f a n do n l yi f c ( g 。) = 1 ( 2 ) l e t rb ea l li n t e g e ra n dr 2 ，t h e n 名( g ) = 力+ ，一2i f a n d o n l yi fc ( g 。) = r f o r ag e n e r a lg r a p hg 、v i t l lm a x i m u m d e g r e ea ，g r i g g sa n d y e h p r o v e d t h a t a ( g 1sa 2 + 2 a n 地u p p e r b o u n dw a s i m p r o v e d t ob e ( g ) a 2 + 2 a 一3w h e ng i s3 - c o n n e c t e da n d 旯( g ) a 2w h e ngi so f d i a m e t e r t w o g r i g g s a n dy e h c o n j e c t u r e dt h a t 五( g ) 印i ng e n e r a l g e r a r dj c h a n ga n dd a v i dk u o 【2 】p r o v e dt h a t a ( g ) s a 2 + af o ra n yg r a p hw i t h m a x i m u md e g r e ea ，b u tt h e r ei ss t i l lag a pi nt h ec o n j e c t u r e 旯( g ) a 2 i ti s d i f f i c u l tt op r o v et h ea b o v ec o n j e c t u r ed i r e c t l y , h e n c er e s e a r c h e r st u m e dt os t u d yt h e u p p e rb o u n d so f ( g ) f o r s o m ec l a s s e so f g r a p h s ，a n dt r yt op r o v et h a tt h e ys a t i s f y t h ea b o v ec o n j e c t u r e t od e s c r i b et h i sp r o b l e mm o r ep r e c i s e l y , g e r a r dj c h a n g 、t k e ，d k u o ，d d f l i ua n dr k y e h 【3 7 】i n2 0 0 0g e n e r a l i z e d t h e l ( 2 ，1 ) - l a b e l i n g s o f g r a p h st ot h ez ( d ，1 ) - l a b e l i n g so ng r a p h sa n dp r o v e dt h a t 乃( g ) a 2 + ( d 一1 ) a f o ra n yg r a p hgw i t hm a x i m u md e g r e e t h e ya l s od e r i v e dt h eu p p e rb o u n d so f ( d ，1 ) - l a b e l i n g so f t r e e s a n do t h e rs e v e r a lc l a s s e so f g r a p h s a l lr e s u l t si nt h i sp a p e ra r em a i n l yd e v e l o p e da r o u n dg r i g g sa n dy e h sc o n j e c t u r e o nt h e l ( 2 ，1 ) - l a b e l i n gp r o b l e mo ng r a p h s w ep a r t l yp r o v e t h a tt h ec o n j e c t u r ei st r u e a n da l s og e n e r a l i z et h e l ( 2 ，1 ) - l a b e l i n gp r o b l e mo ng r a p h s 埘t ld i f f e r e n tp o i n t so f v i e w 1 h i sp a p e ri sd i v i d e di n t of i v ep a r t s ： 1 i nt h ef i r s tp a r tw e p r o v e t h a tt h eu p p e rb o u n d so fl ( 2 ，1 ) l a b e l i n g so f t h e g r a p h s w h i c hw eh a v es t u d i e ds a t i s f yt h ea b o v ec o n j e c t u r e n em a i nr e s u l t sa r ea sf o l l o w s ： t h e o r e m2 2 9 五( g ) 1 0 af o r a n yp l a n a rg r a p hg o fm a x i m u m d e g r e e t h e o r e m2 3 5 z ( s 。( g ) ) 2 af o r a n y 一一s u b d i v i s i o n g r a p hs 。( g ) ( 一23 ) w i t l l m a x i m u m d e g r e e ”一， t h e o r e m2 4 12 ( g ) ( 等) a 2 + 2 af o ra n y k l ( ，l ) 一 订一i n 3f l e e s i m p l eg r a p h gw i t hm a x i m u m d e g r e e a t h e o r e m2 4 2r u n i ts p h e r eg r a p h s ( r 2 ) g 舟a r e 墨。( r ) f l e eg r a p h s ，a n d a ( g r ) 、n 。( 。r 。) h - z 一、( a 2 - r 2 ) + 2 a + r 2 一，( 0 sr s 订( r ) - i ) f o ra n y r - u n i ts p h e r e g r a p hg r ( r 2 ) 、i t l l m a x i m u m d e g r e e a t h e o r e m2 5 1 五( r ( g ) ) s w h e na 6 f o ra n yt o t a lg r a p h 丁( g ) w h e na 6 w i mm a x i m u m d e g r e e t h e o r e m2 6 1f o ra n ys i m p l eb l o c kg r a p h g ，i f t h en u m b e ro fv e r t i c e so f e v e r y b l o c k o fgi sa t l e a s t 3 ，t h e n a ( g ) a 2 t h e o r e m2 , 7 1f o rt h e p r o d u c t gxh ，l e tt h em a x i m u m d e g r e e o f h ：丛 + + 岔 岔 34一2 ，f，【 ：。! ：。一：童查兰堡圭! ! ! ! 垒兰：! ： = ：= g h ，g ，h b ea ，a ( g ) ，a ( h ) r e s p e c t i v e l y , t h e na ( g h ) a 2e x c e p tw h e n o n eo fa ( g ) a n d ( 圩) i sla n da n o 血e r i s n o i e s s t h a n2 ，w h e r e 五( g h ) a 2 + 1 t h e o r e m2 8 1f o rc o m p o s i t i o n g 【h 】，l e t t h em a x i m u md e g r e eo f g h 】， g ，月b ea ，( g ) ，( ) r e s p e c t i v e l y , i f ( g ) 1 ，t h e n 五( g j ? 】) a 2 1 t h e o r e m2 9 1f o r a n y k n e s e r g r a p h gw i t hm a x i m u md e g r e ea ，i f 口一2 b b ，t h e na ( g ) a 2 ；i fo 口一2 b b ，t h e n ( g ) ( ) 口- 2 6 a 2 + 2 a ， a d w h e r e0 ( ) 4 - 2 6 1 ；i fa 一2 b = 0 ，t h e n z ( g ) = 2 ；i f 一6 a 一2 b 0 ，t h e n a d 2 ( g ) = 0 t h e o r e m2 1 0 1 ( g ) s 竺 竺f o ra n y e x t r e m e l yi r r e g u l a rg r a p h gw i t h z m a x i m u m d e g r e e t h e o r e m2 1 1 1f o rt h e m y c i e l s k ig r a p h ( g ) o f ag r a p h g ，i fi t sm a x i m u m tj e g r e ei s ( 卢( g ) ) ，t h e n 工( ( g ) ) s 3 a ( g ( g ) ) t h e o r e m2 1 2 if o rt h ed e s c a r t e s g r a p h ho fa g r a p h g 五( 胃) s 罟( ( 2 ，w h e r e ，o 昔 1 t h e o r e m2 1 3 1 五( g ) g3 + 9f o ra n yh a l i n g r a p h gw i t hm a x i m u m d e g r e e 2 i nt h es e c o n dp a r tw e s t u d yt h el ( d ，1 ) 一l a b e l i n gp r o b l e m o ns e v e r a lp l a n a ra n d r e l a t i v e g r a p h s ，t h e 2 - c h r o m a t i cn u m b e r z 2 ( g ) a n dt h el ( d ，1 ) 一l a b e l i n g s o n g r a p h s ，t h el ( d ，1 ) 一l a b e l i n g s o f 行一s u b d i v i s i o ng r a p h s ，t h e l ( d ，1 ) 一l a b e l i n g s o f r u n i ts p h e r eg r a p h s ，t h el ( d ，1 ) 一l a b e l i n g so f t o t a lg r a p h s ，t h el ( a ，1 ) 一l a b e l i n g so f b l o c kg r a p h s ，t h e z ( a ，】) 一l a b e l i n g s o fp r o d u c tg r a p h s ，t h e l ( d ，1 ) 一l a b e l i n g s o f c o m p o s i t i o ng r a p h s ，t h el ( d ，1 ) 一l a b e l i n g so fk n e s e rg r a p h s ，t h el ( a ，1 ) 一l a b e l i n g s o fe x t r e m e l y i r r e g u l a rg r a p h s ，t h el ( d ，1 ) 一l a b e l i n g s o f m y c i e l s k i g r a p h s ，t h e l ( d ，1 ) 一l a b e l i n g so fd e s c a r t e sg r a p h s ， 3 i nt h et h i r d p a r t w e g e n e r a l i z e t h e l ( 2 ，1 ) 一l a b e l i n g s o n g r a p h s t ot h e l ( d f ，d 2 ) 一l a b e l i n g s o ng r a p h sa n ds t u d yt h e ( 吐，畋) 一l a b e l i n g so nt h eg r a p h s w h i c hw eh a v es t u d i e di nt h es e c o n d p a r t 4 i nt h ef o u r t hp a r tw e g e n e r a l i z et h el ( 2 ，1 ) l a b e l i n gp r o b l e m t oam o r eg e n e r a l c a s e ，i e ，t h e ( 疗，”一l ，1 ) 一l a b e l i n g p r o b l e m 5 i nt h ef i f t hp a r tw e g e n e r a l i z et h el ( 2 ，1 ) - l a b e l i n gp r o b l e mt ot h em o s tg e n e r a l c a s e ，i e ，t h e 三( 吐，d 2 ，以) l a b e l i n g p r o b l e m t h em a i nc r e a t i v ep o i n t so f t h i sp a p e ra r ea sf o l l o w s ： 1 g f i g g sa n dy e hc o n j e c t u r e dt h a t 丑( g ) 蔓a 2f o ra n yg r a p hw i t hm a x i m u md e g r e e w ep r o v et h a tt h e c o n j e c t u r e i st r u ef o rs e v e r a l p l a n a ra n dr e l a t i v eg r a p h s ， n s u b d i v i s i o ng r a p h s ，r u n i ts p h e r eg r a p h s ，t o t a l 铲印l l s ，b l o c kg r a p h s ，p r o d u c t g r a p h s ，c o m p o s i t i o ng r a p h s ，k n e s e rg r a p h s ，e x t r e m e l yi r r e g u l a rg r a p h s ，m y c i e l s k i g r a p h s ，d e s c a r t e sg r a p h s 2 w eg e n e r a l i z et h e l ( 2 ，1 ) - l a b e l i n g so ng r a p h st ot h el ( d l ，d 2 ) 一l a b e l i n g so n g r a p h s ，s t u d yt h e 三( d i ，d 2 ) 一l a b e l i n g so nt h eg r a p h sw h i c hw eh a v es t u d i e di nt h e 6 ： ：堂i 篓篓! ：兰篁! 坠! s e c o n dp a r ta n dg i v et h e i ru p p e rb o u n d so f k 一：( g ) a sc o r o l l a r i e s ，g r i g g s a n d y e h sc o n j e c t u r ei st r u ef o rt h ea b o v es e v e r a lc l a s s e so f g r a p h s 3 w ea l s og e n e r a l i z e t h e l ( 2 ，1 ) 一l a b e l i n g p r o b l e m t o t h e l ( n ，”一1 ，1 ) 一l a b e l i n g p r o b l e ma n d t h el ( d i ，d 2 ，d 。) 一l a b e l i n gp r o b l e m w ep r o v e t h a t t h eu p p e rb o u n d s o ft h e l ( n ，月一1 ，1 ) 一l a b e l i n g a n d l ( d l ，d 2 ，d 。) - l a b e l i n g n u m b e r sc a l lb e r e d u c e dt oa p o l y n o m i a li n o f d e g r e e n 一1 k e yw o r d s ：g r a p h ，c o l o r i n g ，t - c o l o r i n g ，l ( 2 ，1 ) 一l a b e l i n g ，l ( n ，”一1 ，1 ) 一 l a b e l i n g ，l ( d i ，d 2 ，d 。) 一l a b e l i n g 7 山东大学博士学位