（运筹学与控制论专业论文）平方图的染色.pdf

摘要 摘要 图g 的平方图，记作g 2 ，是一个以原图的顶点集为顶点 集，若原图中两点的距离不大于2 则连以边所成的图。对于正 整数p ，q ，n 与图g ，如果函数妒：v ( g ) * o ，1 ，n ) 满足如 下关系：若d i s t c ( u ， ) = 1 则i 妒( 乱) 一妒( ) i p ；若d i s t g ( u ， ) = 2 则l 妒( ) 一妒( ) | q ，那么称函数妒为图g 的l ，q ) - 标号。在所 有l ( p ，口) 一标号中最小的r e 称为( p ，q ) 一跨度，记作a ( g ：p ，q ) 。本 文考虑了下列图类的平方图的色数范围：圈，树，h a l i n 图，外 部平面图以及不含4 到9 圈的平面图。对于外部平面图与不 含4 到9 圈的平面图，本文也给出了它们( p ，g ) 一跨度的界。根 据不含4 到9 圈的平面图的平方图的色数范围的证明方法， 本文给出了一个最多使用+ 6 种颜色来给该图的平方图染 色的o ( 几2 ) 时间算法。最后，本文列出了一些与本文相关的有 意义的没有解决的问题，作为以后研究的一个方向。 【关键词】色数；l ( p ，q ) 一标号；平方图；平面图；外部平面图 中图分类号 0 1 5 7 5 a b s t r a c t t h es q u a r eo fag r a p hg ，d e n o t e db yg 2 ，i sag r a p hw i t ht h es a m e v e r t e xs e ts u c ht h a tt w ov e r t i c e sa r ea d j a c e n ti ng 2i f ft h e i rd i s t a n c ei sa t m o s t2i ng f o ri n t e g e r sp ，q 0 ，al a b e l l i n go fag r a p h 妒：v ( a ) _ o ，1 ，n ，f o rac e r t a i nn 之0 ，i sc a l l e da nl ( p ) 口) 一l a b e l l i n gi fi ts a t i s f i e s ： i 妒( 札) 一妒( u ) i p w h e n e v e rd i s t a ( u ， ) = 1a n dj 妒( ) 一妒( ) i qw h e n e v e r d i s t a ( u ，u ) = 2 t h e ( p ，g ) 一s p a no fag r a p hg ，d e n o t e db ya ( g ；p ，g ) ，i s t h em i n i m u mnf o rw h i c ha n l ( p ，q ) 一l a b e l l i n ge x i s t s i nt h i s a r t i c l ew e c o n s i d e rt h ec h r o m a t i cn u m b e ro ft h es q u a r eo ft h ef o l l o w i n gg r a p hc l a s s e s ： c y c l e s ，t r e e s ，h a l i ng r a p h s ，o u t e r p l a n a rg r a p h sa n dp l a n a rg r a p h sw i t h o u t i - c y c l e s ，w h e r e4sis9 ，a n dg e tar a n g eo ft h ec h r o m a t i cn u m b e ro f t h o s eg r a p h s f o ro u t e r p l a n a rg r a p h sa n d p l a n a rg r a p h sw i t h o u ti - c y c l e s ， w h e r e4 茎is9 ，w ea l s oe x t e n dt h eb o u n do ft h ec h r o m a t i cn u m b e ro f t h o s eg r a p h st ol ( p ，g ) 一l a b e l l i n go ft h e m b yt h ep r o o fo ft h em a i nr e s u l t s o ft h i sa r t i c l e ，w eg i v ea no ( n 2 ) t i m e a l g o r i t h m f o rf i n d i n gac o l o r i n go fg 2 w i t ha + 6c o l o r sa tm o s t a tt h ee n do ft h i sa r t i c l ew ei i s ts o m eu n s o l v e d p r o b l e m sw h i c hi si n t e r e s t e dt oc o n s i d e ri nm y f u t u r es t u d y k e y w o r d s ：c h r o m a t i cn u m b e r ；l ( p ，口) 一l a b e l l i n g ；s q u a r eo fag r a p h p l a n a rg r a p h ；o u t e r p l a n a rg r a p h c l cn u t u b e r ：0 1 5 7 5 果。 学位论文独创性声明 本人郑重声明； i 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名：盐垒篮 日 期：丝望垒、盘。7 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子 版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文 进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行 检索i 有权将学位论文的标题和摘要汇编出版保密的学位论文在解 密后适用本规定。 作者签名：盐生簦 日期l 2 碰垡= 垒。f 2 a c k n o w l e d g e m e m s a c k n o w l e d g e m e n t s w i t ht h eu l o l n e n to ff i n i s h i n gm yt h r e ey e a r sp o s t g r a d u a t es t u d e n t s t u d yi nt h i sb e a u t i f u lu n i v e r s i t yc o m i n g t h et i m ei sm a t u r ef o rr i l et oe x p r e s sm y h e a r t f e l ta n d l o n g l a s t i n gg r a t i t u d et om yt u t o r s ：f a m i l ym e m b e r s a n dm yc l a s s m a t e s m yi n d e b t e d n e s sg o e st op r o f e s s o rx ub a o g a n g ，w h o s ep r o f e s s i o n a l d e v o t i o nt ot h es t u d e n t s g r o w t ha n ds t y l eo fs e e k i n gt r u es c h o l a r s h i ph a v e a l w a y sb e e nap o i n to fr e f e r e n c ee v e r yt i m eit a k eu pm y r e s e a r c ha n dw i l l i n f l u e n c em ei nt h ef u t u r eio w em yg r o s sg r a t i t u d et ol l i m a sh i sah a l f y e a rj n s t r u e t i o n so n “g r a p ht h e o r y ”“c o m b i n a t o r i c s a n d0 p t i m i z e ”a n d ay e a ri n s t r u c t i o n so n “s e l e c t e dr e a d i n g so fg r a p ht h e o r yl i t e r a t u r e ” h a v ed e e p e n e dm yu n d e r s t a n d i n go ft h eg r a p ht h e o r ya n de x p a n d e dn a y v i s i o no fc o l o r i n gp r o b l e m s h i sr i g i dl o g i c a lt h i n k i n gh a si m p r e s s e da n d e n l i g h t e n e dm et n u c h i ti s p r o f e s s o rx uw h oh a sb r o u g h tm ei n t ot h e w o r l do fg r a p hr e s e a r c ha n di n t r o d u e e di 掣t f ft om e w i t h o u th i sp a t i e n t a n dm e t i c u l o u sg u i d a n c e i tw o u l dl l a v eb e e ni m p o s s i b l ef o rm et og e tt h i s a r t i c l ec o m p l e t e d ia me x t r e m e l yg r a t e f u lf o rt h eu s e f u ls u g g e s t i o n sg i v e n b vp r o f e s s o rx uo nt h i sa r t i c l e h i sk i n d e s th e l pa n dg e n e r o s i t yw i l lb e l o c k e di ni n yl i e a r tf o r e v e r ， m ye s p e c i a lt h a n k sg ot op r o f e s s o rz h o ux i n g h e ，d o c t o rs u nz h i r e n a n dd o c t o rz l m n gx u e b i n m yf u n d a m e n t a li d e a sa b o u tg r a p ht h e o r y i n s p i r e db yp r o f e s s o rz h o u so n ey e a rj n s t r u c t i o n so i l “g r a p ht h e o r y ”h e i ss u c hap r e c i s e c a r e f i t lt u t o rt h a ti t g a v em ed e e pi m p r e s s i o na n ds e ta g o o de x a m p l e f o rm et ot e a c hs t u d e n t so fm y s e l fi nt h ef u t u r e d o c t o rs u n w h oi sah i g h l yi n t e l l i g e n tt u t o rt a u g h tm et h ec o u r s e “c o m b i n a t o r i c s ” w h i c hi sv e r yh e l p f u lf o rm et os t u d yo t h e rr e l a t i v ec o u r s e s 1w i l la l w a y s o w ead e b to fg r a t i t u d et od o c t o rs u nf o rh i sk i n d n e s s ，c a r ea n dh e l p d u r i n gm y t h r e ey e a r s s t u d y ia l s ot h a n kd o c t o rz h a n gf o rh i sh a l f - y e a r i n s t r u c t i o no n “c o m b i n a t o r i a ld e s i g n s ”w h i c hb r o a d e n sm yh o r i z o n s m y s i n c e r et h a n k sg ot oa 1 1m y f a m i l ym e m b e r s ，e s p e c i a lm y m o t h e r m ym o t h e ri s ag r e a tm o r ni 1 2t h ew o r l dj nm y e y e s ，d u r i n gt h et h r e e y e a r s1w a si nn a n j i n g ，m yf a t h e rh a db e e ni nh o s p i t a lt w i c e ，o n ef o ra n i m p o r t a n th e a r to p e r a t i o n m ys i s t e rh a da na c c i d e n ta n da l s oh a db e e n i nac o l n af o rd a y si nh o s p i t a la f t e ra nu r g e n ts u r g e r yo nb r a i n t h e r ei s a c k n o w l e d g e j n e j 】s n od o u b tt h a tm ym u mn e e dm em o s ta tt h ec r i t i c a lm o m e n to fm y f a m i l y 、 b u tic a l ln o ts t a yl o n gt oh e l ph e ro re v e nt o n i f o r th e r 1w i l ln e v e r f o r g i v e m y s e l ff o rt h i s t h o u g ha l l t h e s em i s f o r t u n ee v e n t sb e f e l lo nm yf a m i l y , b o t hm yf a t h e ra n ds i s t e rg o tb e t t e ra n db e t t e ru n d e rm ym o t h e r sc a r e t h a n ka l lm y f a m i l i e s ，a n dia ml o o k i n gf o r w a r dt ol i v i n gw i t hy o um o n t h s 1 a t e ra n df o ra 1 1f u t u r et i m e f i n a l l y , ia mg r a t e f u lf o rm y c l a s s m a t e sa n dr o o m m a t e s d u r i n gt h e t h r e ey e a r s ，t h e yg a v em eg e n e r o u sh e l pf o r m ys t u d ya n dl i f e a l lm y c l a s s m a t e sa r eg o o da tt h e i rw o r k ，a n dt h e i re x c e l l e n c ee n c o u r a g e sm et o w o r kh a r da t e v e r ym o m e n t ia l s ot h a n km yr o o m m a t e sf o rc r e a t i n g c o m f o r t a b l es t u d ye n v i r o n m e n tf o rm e t h r e ey e a r ss t u d yi nt h i sb e a u t i f u lu n i v e r s i t yw i t hm yt u t o r s m y c l a s s m a t e sa n dr o o m m a t e sl e a v e sb e s tm e m o r yi nm ym i n d1w i l lc h e r i s h t h e mf o r e v e r 1 i n t r o d u c t i o n 1 1 b a s i cd e f i n i t i o n sa n dt e r m i n o l o g i e s 、 ，ea s s u n l et h a tt h e g i v e ng r a p hg i sac o n n e c t e ds i m p l ef i n i t eg r a p h t h es e to fv e r t i c e s ，e d g e sa n df a c e so fg a r ed e n o t e db y 矿( g ) ，e ( c ) a n d f ( g ) ，r e s p e c t i v e l y w jc a l li v ( c ) ia n di e ( c ) it h e o r d e ro fga n dt h es i z e o fg r e s p e c t i v e l y ag r a p hg i ss a i dt ob ea no u t e r p l a n a rg r a p hi fi tc a n b ed r a w ni nt h ep l a n ei ns u c haw a yt h a ta l 】v e r t i c e sa r eo nt h eb o u n d a r y o fas a m ef a c e t h el e n g t ho fap a t hb e t w e e nt w ov e r t i c e si st h en u m b e r o fe d g e so nt h a tp a t h w d e f i n et h ed i s t a n c eb e t w e e nt w ov e r t i c e sua n d v ，d e n o t e db yd i s t a ( u ，u ) ，t ob et h el e n g t ho ft h es h o r t e s tp a t hb e t w e e n t h e m t h es q u a r eo fag r a p hg ，d e n o t e db yg 2 ，i sag r a p hw i t ht h es a m e v e r t e xs e ts u c ht h a tt w ov e r t i c e sa r ea d j a c e n ti ng 2i f ft h e i rd i s t a n c ei n gi s2a tm o s t t h ed e g r e eo fav e r t e xui st h en u m b e ro fe d g e si n c i d e n t w i t hv ，d e n o t e db yd g ( v ) o rs i m p l yd ( v ) ，i fi t i sn o tc o n f u s i n g w ed e n o t e t h em s x i n l u md e g r e eo fag r a p hg b ya ( g ) o rs i m p l ya a n dd e n o t et h e m i n i m u m d e g r e eo fag r a p hgb y6 f g lo rs i m p l yd i ft h ed e g r e eo fv i si ， a t1 e a s tio ra tn l o s tiw ec a l li ta ni - v e r t e x ，a i - v e r t e xo ra 茎i v e r t e x ， r e s p e c t i v e l y t h ed e g r e e ，d a ( f ) o rs i m p l yd ( ，) ，o faf a c efi s t h en u m b e r o fe d g e sw i t hw h i c hi ti si n c i d e n t c u te d g e sb e i n gc o u n t e dt w i c e i ft h e d e g r e eo faf a c ei si ，w ec a l l i tai - f a c e am a x i m a lc o m p l e t es u b g r a p h o fag r a p hi sc a l l e dac l i q u e ag r a p hgi sc o n n e c t e di fa n yt w oo fi t s v e r t i c e sc a l lb ei o i n e db yap a t h ，o t h e r w i s ei t i sd i s c o n n e c t e d at r e ei sa c o n n e c t e da c y c l i cg r a p h n a ma n dn a ( v ) d e n o t et h en e i g h b o r so fvi ng i n c l u d i n gua n de x c l u d i n gv ，r e s p e c t i v e l y am a x i m a l c o n n e c t e ds u b g r a p h o fag r a p hgi sac o m p o n e n to fg ac u tv e r t e xi sav e r t e xw h o s ed e l e t i o n i n e r e a s e st h en u m b e ro fc o m p o n e n t s ac o n n e c t e dg r a p ht h a th a sn oc u t v e r t i c e si sc a l l e dab l o c k ab l o c ko ag r a p hi sas u b g r a p ht h a ti s a b l o c ka n di sm a x i m a lw i t hr e s p e c tt ot h i sp r o p e r t y , i fgi sc o n n e c t e da n d f o rs o m es e two fv e r t i c e s ，g wi sd i s c o n n e c t e d ，t h e nw es a yt h a tw s e p a r a t e sg f o r 南 2 w es a yt h a tag r a p hg i sk - c o n n e c t e di fe i t h 6 rg i sac o m p l e t eg r a p hk k + lo re l s ei th a sa tl e a s tk + 2v e r t i c e sa n dn os e t o fk 一1v e r t i c e ss e p a r a t e si t g i v e na ne d g eu uo fag r a p hg t h eg r a p h g u vi s an e wg r a p ho b t a i n e df r o mg b yc o n t r a c t i n gt h ee d g eu v t h a t 2 i s t og e tg l u t ，w ei d e n t i f yt h ev e r t i c e sua n d a n d r e m o v ea l lr e s u l t i n g l o o p sa n dd u p l i c a t ee d g e s ag r a p hg h a sag r a p hh a l sam i n o ri fhc a n b eo b t a i n e df o r mas u b g r a p ho fgb yc o n t r a c t i n ge d g e s ，a n dg i sc a l l e d h m i n o rf r e ei fgd o e sn o th a v eh a sam i n o r a v e r t e xk - c o l o r i n g o f a g r a p h g i s a m a p p i n gc ：v ( a ) _ 1 ，2 ，t ，七) s u c ht h a ta l l yt w oa d j a c e n tv e r t i c e s 札a n dva r em a p p e dt od i f f e r e n ti n t e - g e t s t i l em i n i m u m 忌f o r w h i c hak - c o l o r i n ge x i s t si sc a l l e dt h ec h r o m a t i c n u m b e ro fga n di sd e n o t e db yx ( g ) g i v e nag r a p hga n dam a pl a s s i g n i n gt o e a c hv e r t e xas e tl ( x ) ，a nl c o l o r i n go fgi s ac o l o r i n gc o ft h ev e r t i c e ss u c ht h a tc ( x ) l ( x ) f o re v e r yz y ( g ) t h el i s t c h r o m a t i cn u m b e rc h ( g ) o fg i st h em i n i m a l i n t e g e rks u c ht h a tg h a sa n l c o l o r i n gw h e n e v e ri l ( x ) i = k f o re v e r yz v ( a ) f o ri n t e g e r sp ，q 0 ， al a b e l l i n go fag r a p h 妒：v ( a ) 一 o ，1 ，n ) ，f o rac e r t a i n 佗0 ，i s c a l l e da nl ( p ，口) 一l a b e l l i n gi fi ts a t i s f i e s ： ( 1 ) l 妒( “) 一妒( 削) l2p w h e n e v e rd i s t a ( u ，u ) = l ； ( 2 ) l 妒( u ) 一妒( u ) l qw h e n e v e rd i s t a ( u ， ) = 2 t h e ( p ，口) 一s p a n o fag r a p hg ，d e n o t e da ( g ；p ，口) ，i st h em i n i m u mnf o r w h i c ha nl ( p ，q ) 1 a b e l l i n ge x i s t s i ti se a s yt os e et h a td e t e r m i n i n ga ( g ；1 ，0 ) i st of i n d i n gt h ec h r o m a t i cn u m b e rx ( c ) a n dt h ep r o b l e mo ff i n d i n ga n l ( 1 ，1 ) 一l a b e l l i n ga m o u n t s t of i n d i n gac o l o r i n go ft h es q u a r eo fg w ec a n s e et h a tt i l ef o l l o w i n gh o l d s ：x ( a 2 ) = a ( g ；1 ，1 ) + 1 o t h e rt e r m i n o l o g i e s a n dn o t a t i o n su s e di nt h i sa r t i c l ea r er e f e r r e di n 1 】 2 1 2b a c k g r o u n da n dk n o w n r e s u l t s t h em a i ni n s p i r a t i o nf o rl ( p ，g ) 一l a b e l l i n gc o m e sf o r mt h ec h a n n e la s s i g n m e n tp r o b l e mi nr a d i oa n d c e l l u l a rp h o n es y s t e m s ，w h e r ee a c hv e r t e x o ft h eg r a p hc o r r e s p o n d st oat r a n s m i t t e rl o c a t i o n ，w i t ht h el a b e la s s i g n e d t oi td e t e r m i n i n gt h ef r e q u e n c yc h a n n e lo nw h i c hi tt r a n s m i t s i na p p l i c a t i o n s ，b e c a u s eo fp o s s i b l ei n t e r f e r e n c eb e t w e e nn e i g h b o r i n gt r a n s m i t t e r s ， t h ec h a n n e l sa s s i g n e dt ot h e mm u s th a v eac e r t a i nd i s t a n c ef r o me a c ho t h e r as i m i l a rr e q u i r e m e n ta r i s e sf o r mt r a n s m i t t e r st h a ta r en o tn e i g h b o r sb u t a r ec l o s e i ea td i s t a n c e2 t h i sp r o b l e mi sa l s ok n o w na 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 m b e c a u s e o ft h em o t i v a t i n ga p p l i c a t i o nf o rt h i sp r o b l e m ，i ti sq u i t en a t u r a lt oc o n s i d e ri t o np l a n a rg r a p ht h eq u e s t i o no f 3 f i n d i n gt h eb e s t , p o s s i b l eu p p e rb o u n df o r t h ec h r o m a t i cn u m b e ro ft h e s q u a r eo f ap l a n a rg r a p hs e e m st of i r s th a v eb e e nb r o u g h tu pb yg w e g n e r 3 i l l 1 9 7 7 h ep r o p o s e dt h ef o l l o w i n gc o n j e c t u r e ： c o n j e c t u r e1 、( g w e g n e rf 3 1 ) f o r ap l a n a r g r a p hg ： x ( a 2 ) + 5 i f4 茎as7 2 + 1 i f8 g w e g g e r a l s og a v e e x a m p l e si l l u s t r a t i n gt h a tt h eb o u n d s a r eb e s tp o s s i b l e a n ds h o w e dt h a ti fa=3t h e nt h es q u a r eo fgc a nb e8 - c o l o r e d h e c o n j e c t u r e dt h a ti nf a c t7c o l o r sw o u l db ee n o u g h r e c e n t l y ，t h o m a s s e n 4 h a ss o l v e dt h i sc o n j e c t u r ef o ra = 3 ，b ys h o w i n gt h a tt h es q u a r eo f e v e r yc u b i cp l a n a rg r a p hi s 7 - c o l o r a b l e j v d h e u v e la n ds m g u i n n e s s 5 s h o w e dt h a t i fgi sap l a n a rg r a p hw i t hm a x i m u md e g r e e ，t h e n x ( a 2 ) 2 a + 5 ，g a g n a r s s o na n dm m h a l l d 6 r s s o nf 6 7 h a v eab e t t e r a s y m p t o t i cb o u n d f o rl a r g ev a l u e so f t h e yp r o v e dt h a ti fgi sa p l a n a r g r a p hw i t ha 7 4 9 ，t h e nx ( a 2 ) _ 。9a j + 2 o vb o r o d i ne ta 1 7 ：8 h a v eb e e na b l et oe x t e n dt h i sr e s u l tf u r t h e rb yp r o v i n g x ( a 2 ) 【：j + 1 f o rp l a n a rg r a p hw i t h 4 7 t h eb e s tk n o w nb o u n df o rx ( a 2 ) f o r g e n e r a l p l a n a rg r a p hi sd u e t om m o l l o ya n dm r ，s a l a v a t i p o u rf 9 = t h e o r e m1 1 ( m m o l l o ya n dm r s a l a v a t i p o u r 嘲) f o rap l a n a rg r a p h g ，x ( c 2 ) ；1 + 7 8 t h e o r e m1 2 ( m m o l l o ya n dm rs a l a v a t i p o u ri 9 ) f o rap l a n a rg r a p h g ，矽a 2 4 1 ，t h e nx ( a 2 ) f i 5 + 2 4 ， f o ra p l a n a rg r a p h t h eb e s tk n o w nu p p e rb o u n df o ra ( g ；p ，g ) i sa l s og i v e n b ym m o l l 0 3 7a n dm r s a l a v a t i p o u r 9 a sf o l l o w s ： t h e o r e m1 3 i m m o l l o ya n dm , r s a l a v a t i p o u r ) f o ra n yp l a n a rg r a p h ga n d p o s i t i v ei n t e g e r pa n dq ：a ( g ；p ，q ) 茸f ；1 十1 8 p + 7 7 q 一1 8 i n s t e a do fc o n s i d e r i n gg e n e r a lp l a n a rg r a p h ，k w l i he t a 1 1 0 s t u d i e d c o l o r i n gt h es q u a r eo fa ( 4 一m i n o rf r e eg r a p h ，a n dg e tt h ef o l l o w i n gr e s u l t ： t h e o r e m1 4 ( k 。w l i he ta 1 1 0 | ) l e tgb ea i q m i n o r f r e eg r a p h t h e n x ( g 2 ，f ，；盆= = ；i i ；2 丢簧3 t h e ya l s og a v ee x a m p l e st os h o wt h a tt h er e s u l ta b o v ei sb e s tp o s s i b l e ，jj【 4 w h e nw ec o n s i d e rl i s tc h r o m a t i cn u m b e ro fg ，i ti s e a s y t os e e c h ( g ) x ( g ) w e c a n s e e ( b yc o n s i d e r i n gc o m p l e t e - b i p a r t i t eg r a p h s ) t h a t t h e r ei sn ou p p e rb o u n df o rc h ( g ) i nt e r m so f x ( a ) i ng e n e r a l t h o u g ht h e a b o v ef a c t ，t h o m a s s e n 【1 1 c l a i m e dt h a tu n d e rc e r t a i nc i r c u m s t a n c e st h e l i s t c h r o m a t i cn u m b e ri sn o tm u c hl a r g e rt h a nt h ec h r o m a t i cn u m b e rb y p r o v e dt h a tv e r yp l a n a rg r a p h i s5 - c h o o s a b l e b u tb yv o i g t 1 2 ，w ek n o w n t h a tp l a n a rg r a p ha r en o t4 - c h o o s a b l e t h e r ea r es e v e r a lc l a s s e so fg r a p h s gf o rw h i c hi ti sc o n j e c t u r e dt h a tc h ( o ) = x ( a ) i n c l u d i n gt h ef o l l o w i n g c o n j e c t u r eb ya v k o s t o c h k aa n dd rw o o d a l l 1 3 ： c o n j e c t u r e1 2 ( a v k o s t o