（运筹学与控制论专业论文）无指定构型平面图的选色与不完全选色性.pdf

果。 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均己在论文中作了声明并表示了 谢意。 作者签名：垂鲨鸳 日 期：丛翌竺：竺兰 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行检 索：有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密 后适用本规定。 作者签名： 日期： 器造簿 趔竺：幺：兰 a b s t r a c t t h ec h o i c en u m b e ro fag r a p hg ，d e n o t e db yx f ( g ) ，i st h em i n i m u mn u m b e r s u c ht h a ti fw e g i v eal i s to fkc o l o r st oe a c hv e r t e xo fg t h e r ei sa v e r t e xc o l o r i n g o fgw h e r ee a c hv e r t e xr e c e i v e sac o l o r r o i l i t so w ni i s tn om a t t e rw h a t h ei i s t s a r e 。i nc h a p t e r2 ，w es h o wt h a t 船( g ) s3f o ra l lp l a n a rg r a p h so fg i r t hn o tl e s s t h a n4w h i c h ( i ) c o n t a i n sn o5 - a n d6 - c i r c u i t so r ( i i ) c o n t a i n sn o7 一a n d8 - c i r c u i t s o r ( i i i ) c o n t a i n sn o 8 一a n d9 - c i r c u i t s ，w ea l s os h o wt h a t ( g ) s3f o re a c hp a n a r g r a p ho fg i r t hn o tl e s st h a n4w h i c hc o n t a i n sr i o6 ，7 一a n d9 - c i r c u i t s w ea l s od i s s c n s sd e f e c t i v ec h o o s a h i l i t yi n c h a p t e r3 ag r a p hc i sc a f f e d ( k ，d ) 一c h o o s a b l ei f f o re v e r y l i s ta s s i g n m e n tl s a t i s f y i n gl l ( v ) l = kf o ra l l y ( g ) ， t h e r ei sa nl c o l o r i n go fgs u c ht h a te a c hv e r t e xo fgh a sa tm o s tdn e i g h b o r s c o l o r e dw i t ht h es h a l ec o l o ra si t s e l eh ic h a p t e r3 as t r u c t u r a lt h e o r e ma b o u t t o r o i d mg z a p h si sg i v e nt h a ts t r e n g l ，h e n sar e s u l to fb o r o d i n 1 3 o np l a n eg r a p h s a sac o n s e q u e n c e ，w es h o wt h a te v e r yt o r o i d a lg r a p hw i t h o u ta d j a c e n tt r i a n g l e s i s ( 4 ，1 ) * - c h o o s a b l e al i n e a rt i m ea l g o r i t h mf o rp r o d u c i n gs u c hac o l o r i n g i s p r e s e u t e da l s o i na d d i t i o n ，w ep r o v et h a te v e r yp l a n a rg r a p hw i t h o u t4 - c i r c u i t s a n d i n t e r s e c t i n gt r i a n g l e si s ( 3 11 ) c h o o s a b l e k e y m o r d s ：c i r c u i t s ，g i r t h ，p l a n a rg r a p h jl i n e a ra l g o r i t h m ，c h o o s a b i l i y d e f e c t i v ec h o o s a b i l i t y ； a m s2 0 0 08 u b d e c tc l a s s i f i c a t i o n s ：f 1 5 c 1 5 ，0 5 c 7 8 ； g 五cn m b e r ? 0 1 5 75 1 摘要 图g 的选色数，记为( g ) ，定义为最小的自然数k ，使得满足：对 任一顶点给定k 种颜色的列表，且染色时每个顶点的颜色只能从自身 的颜色列表中选择时，总存在图g 顶点的一个正常着色。在第二章， 论文证明了每个围长至少为4 且不含( t ) 5 一圈和6 圈或( i i ) 7 一圈和8 一圈 或( i i i ) s 圈和9 圈的平面图是3 ，可选色的。同时还证明了每个围长至 少为4 且不含6 一圈，7 一圈和9 圈的平面图是3 可选色的 我们还讨论了不完全选色的相关问题若对任一顶点给定k 种颜色 的列表，染色时每个顶点的颜色只能从自身的颜色列表中选择且每个 顶点至多有d 个邻点染相同的颜色，总存在图g 的一个顶点的正常着 色，则图g 称为( k ，d ) t - 可选色的在第三章，论文给出了关于轮胎图 的一个结构性的定理，此定理加强了b o r o d i n 在【1 3 】中的关于平面图的 类似结论。运用此定理，证明了每个没有相邻三角形的轮胎图是( 4 ，1 ) 一 可选色的。论文还给出了寻找这样一种着色的线性时间的算法。此外， 论文还证明了每个无4 圈和相交三角形的平面图是( 3 ，1 ) t 可选色的。 陕键词1 圈，围长，平面图，线性算法，选色性，不完全选色性； 2 1i n t r o d u c t i o n 1 1b a s i cd e f i n i t i o n sa n dn o t a t i o n s t h r o u g h o u tt h i sw o r kw ec o n s i d e ro n l yf i n i t e ，u n d i r e c t e d ，i o o p l e s s ，a n dw i t h o u t m u l t i p l ee d g e su n l e s ss t a t e do t h e r w i s e o t h e rn o t a t i o n sf o l l o w st h a to fb o n d y a n dm u r t y 2 5 g = ( u e ，f ) d e n o t e sap l a n a rg r a p h ，w i t hv ，ea n dfb e i n g 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 r e s p e c t i v e l y i fe = u v i sa ne d g eo fg ， t h e nei ss a i dt oj o i nv e r t i c e sua n du 、札a n d a r es a i dt ob ea d j a c e n ta n du ( o ro ) i ss a i dt ob ei n c i d e n tw i t ht h ee d g ee t w oe d g e sea n de a r ea d j a c e n ti ft h e ya r e i n c i d e n tw i t hac o m m o nv e r t e x t h ed e g r e eo fav e r t e xui nag r a p hg ，d e n o t e d a sd a ( ) ，i st h en u m b e ro fe d g e si ngi n c i d e n tw i t hu ，t h em a x i m u md e g r e eo f a l lv e r t i c e si ngi sd e n o t e db y f g la n dt h em i n i m u md e g r e eo fa 1 1v e r t i c e si ng i sd e n o t e db y6 ( g ) l e tn g ( u ) ( o rs i m p l y ) ) d e n o t et h es e to fn e i g h b o r so fa v e r t e x “i n g a g r a p hh i sas u b g r a p ho ft h eg r a p hg ( w r i t t e nhc g ) i fv ( h ) i s as u b s e t o fv ( a ) a n de ( h ) i sas u b s e to fe ( g ) s u p p o s ehc v ( c ) a n d i sn o n e m p t y , t h es u b g r a p ho fgw h o s ev e r t e xs e ti s “a n dw h o s ee d g es e ti st h es e to ft h o s e e d g e so fg t h a th a v eb o t he n d si nki sc a l l e dt h es n b g ：r a p ho fgi n d u c e db y 。 a s u b g r a p hh i sa s p a n n i n gg r a p h o fgi sv ( h ) = v ( g ) t w oc i r c u i t so rf a c e sa r ei n t e r s e c t i n gi ft h e ys h a r ea tl e a s to n ec o m m o nb o u n d a r yv e r t e x t w of a c e so fap l a n eg r a p ha r es a i dt ob en 由a c e n ti ft h e yh a v ea t l e a s to n ee o i u m o l lb o u n d a r ye d g e w eu s eb ( f ) t od e n o t et h eb o u n d a r yo faf a c e ，a n du s en f ，) t od e n o t et h es e to ff a c e sa d j a c e n tt o af a c ei si n c i d e n tw i t h a l lv e r t i c e sa n de d g e so ni t sb o u n d a r yb ( f 1 ak v e r t e xi sav e r t e xo fd e g r e ek a n da 七十一( o r 一) v e r t e xi sav e r t e xo fd e g r e e a tl e a s t ( o ra tm o s t ) 七t h ed e g r e eo faf a c efo fg ，d e n o t e db yd g ( f ) ，i st h en u m b e r o fe d g e si n c i d e n tw i t hi t ，w h e r ec u te d g e sa r ec o u n t e dt w i c e ，i fd a ( ，) = k ，t h e n fi sc a l e dak f a c e a 角+ 一f o rk 一) f a c e ，i saf a c eo fd e g r e ea tl e a s t ( o ra tm o s t ) k ak - c i r c u i ti sac i r c u i to nkv e r t i c e s ，t h ev e r t e xs e to fac i r c u i tcw i l la l s ob e d e n o t e db yc t h es e to fa l l 七c i r c u i t so fgi sd e n o t e db yo ag r a p hi sc a l e d g k f r e ei f 仇= 曲t h eg i r t ho fg i st h el e n g t ho fas h o r t e s tc i r c u i to fg av e r t e x a n daf a c efa r es a i dt ob ei n c i d e n ti ful i e so nt h eb o u n d a r yo f f f o rz v ( a ) uf ( g ) ，w eu s e 以( o ) t od e n o t et h es e to fa l lk - f a c e st h a ta r e i n c i d e n to ra d j a c e n tt oz ，a n dy k f x ) t od e n o t et h es e to fa l lk v e r t i c e st h a ta r e i n c i d e n to ra d j a c e n tt oo f o r ，f ( g ) ，w ew r i t e ，= = f 嚣1 让2 - u n 】i fu l ，让2 ，一， t 上n a r et h eb o u n d a r yv e r t i c e so f ，i nt h ec l o c k w i s eo r d e r an f a c e 【乱l t 上2 札3 “n l i sc a l l e da n ( m l ，m 2 ，m 3 ，帆i ) - f a c ei f d ( u i ) = 帆f o ri = 1 ，2 ，3 ，一，n at o r n si sac l o s e ds u r f a c e ( c o m p a c t c o n n e c t e d2 一m a n i f o l d sw i t h o u tb o u n d a r y l t h a ti sas p h e r ew i t hau n i q u eh a n d l e a n dat o r o i d a lg r a p hi sag r a p h2 一e e l l e m b e d a b l eo nt h et o m sf o rat o r o i d a lg r a p hg w es t i iu s egt od e n o t ea2 e e l l 3 e m b e d d i n go fg o nt o m s ag r a p hgi sc a l l e dap l a n a ri fi tc a d _ b ed r a w ni nt h e p l a n e ，s u c ht h a ti t se d g e si n t e r s e c to n l ya tt h e i rv e r t i c e s a g r a p hg i sc a l l e dac h a r d a 2g r a p hi fi td o e sn o tc o n t a i na ni n d u c e ds u b g r a p h w h i c hi sac i r c u i to fl e n g t hg r e a t e rt h a n3 t h ec o r eo fag r a p hg i st h es u b g r a p h w h i c hr e i n a i n sa f t e rs u c c e s s i v er e m o v a lo fa 1 1v e r t i c e so fd e g r e eo n e ag r a p hgi s c a l l e dd d e g e n e r a t ei fe v e r ys u b g r a p ho fgc o n t a i n sa tl e a so n ev e r t e xo fd e g r e e a tm o s td ag r a p hgi sc a l l e dae p 一g r a p hi fi tc o n s i s t so ft w ov e r t i c e sa l a n da 2a n dt h r e ei n t e r n a l l yd i s j o i n tp a t h so fl e n g t h sp ，r ，a n dsj o i n i n ga la n da 2 am i n i m a l l yn o n - 3 一c h o o s a b i eg r a p hi sag r a p hw h i c hi sn o t3 - c h o o s a b l e b u t e v e r yo f i t sp r o p e ri n d u c e ds u b g r a p hi s3 c h o o s a b l e i ti sc l e a r l yt h a te v e r yv e r t e x o f8m i n i m a l l y1 2 0 1 1 - 3 - c h o o s a b l eg r a p hh a sd e g r e ea t1 e a s t3 d e f i n i t i o n1 ：a nh - f a c e ，i sc a l l e da l i g h th - f a c ei fa l li n c i d e n t a lv e r t i c e sa r e 3 一一 v e r t i c e s o t h e r w i s ean o n l i g h th - f a c ei fi ti si n c i d e n tw i t ha tl e a s to n e4 + - v e r t e x d e f i n i t i o n2 ：a nh f a c ei sc a l l e dam i n i m a lh - f a c ei fi tl i e so ne x a c t l yo n e4 - v e r t e xa n d3 - - v e r t e xo no t h e rv e r t i c e s ，s i m i l a r l y ，ah - f a c ei sc a l l e da ? 2 。n m i n i m a l h - f a c ei fi tl i e so na tl e a s tt w o4 + v e r t e x ac o l o rl i s tl = l ( v ) ：y i sa f a m i l yo fc o l o rs e t sa s s i g n e dt oe a c hv e r t e x o fg a nl - c o l o r i n go fgi sa na s s i g n m e n tt oe a c hv e r t e xv vf r o ml ( v 1s u c h t h a ta d j a c e n tv e r t i c e sr e c e i v ed i s t i n c tc o l o r s ag r a p hgi sc a l l e dk - c h o o s a b l ei f ga d m i t sa nl c o l o r i n gf o re a c hc o l o r - l i s tlw i t h c o l o r si ne a c hl i s t t h ec h o i c e n u m b e ro fg ，d e n o t e db y 2 ( g ) ，i st h em i n i m u mks u c ht h a tgi sk c h o o s a b l e t h i sp a r a m e t e ri sa l s ok n o w na st h ec h o o s a b i l i t y 2 a n dt h el - c o l o r i n go fa g r a p h gw i t hi l ( v ) i = i sa l s ok n o w n a st h ek 。l i s tc o l o r i n g l e tmb ea n p o s i t i v ei n t e g e r ag r a p hg i sm - c o l o r a b l ew i t hi m p r o p r i e t yd o r s i m p l y ( m ，d ) c o l o r a b l e ，i ft h ev e r t i c e so fg c a nb ec o l o r e dw i t hmc o l o r ss ot h a t e a c hv e r t e xh a sa tm o s tdo ft h es a m ec o l o r8 si t s e l f a nf m ，0 ) + 一c o l o r i n gi sa n o r d i n a r yp r o p e rm - c o l o r i n g al i s ta s s i g n m e n to fg i saf u n c t i o nlt h a ta s s i g n sa l i s tl ( v ) o fc o l o r st oe a c hv e r t e x y ( g ) a nl - c o l o r i n gw i t hi m p r o p r i e t yd ，o r s i m p l y ( l ，d ) - c o l o r i n g ，i sam a p p i n g t h a ta s s i g n sac o l o r ( 口) ( 甜) t oe a c h v e r t e x v ( v ) s u c h t h a tvh a sa tm o s td n e i g h b o r sc o l o r e dw i t h ( 口) ag r a p h i sm - c h o o s a b l ew i t hi m p r o p r i e t yd ，o rs i m p l y ( m ，d ) + c h o o s a b l e ，i ft h e r ee x i s t s a n ( l ，d ) l c o l o r i n gf o re v e r yl i s ta s s i g n m e n tlw i t hl l ( v ) i = mf o ra l l v ( g ) o b v i o u s l y , e v e r yk - c h o o s a b t eg r a p hi s ( k ，d ) c h o o s a b t e 1 2 b a c k g r o u n da n ds o m ek n o w nr e s u l t s o n eo ft h em o s ti n t r i g u i n gc l a s s e so fg r a p h sf r o mt h ep o i n to fv i e wo fc o l o r i n g p r o b l e m si s t h ec l a s so fp l a n a rg r a p h s o n eo ft h er e a s o n sf o rt h i sf a c ti st h e4 - 4 c o l o rp r o b l e m ，w h i c hr e m a i n e du n s o l v e df o rm o r et h a n1 2 0y e a r s ( 1 8 5 2 1 9 7 7 ) a n d g a v eas t r o n gs t i m u l u st ot h ed e v e l o p m e n to fg r a p ht h e o r y 4 - c o l o u r - p r o b l e m i si t p o s s i b l et oc o l o u rt h ec o u n t r i e so f a n a r b i t r a r ym a pu s i n ga tm o s t f o u r c o l o u r ss ot h a te v e r yt w oc o u n t r i e sw h i c hh a v eab o r d e r l i n ei nc o m m o ng e t d i 行e r e n tc o l o u r s ? i n1 9 7 7 ，a p p e l ，h a k e na n dk o c h 2 6 ，2 7 lp r o v e dt h e4 一c o l o u rt h e o r e mw h i c h g v e s a p o s i t i v ea l l s w e rt ot h ea b o v eq u e s t i o n a s s u m et h a te v e r yc o u n t r yc h o o s e s as e to fa l l o w e dc o l o u r s n o wac o l o u r i n go ft h ec o u n t r i e sm u s ta l w a y su s eo n e o fi t so w ne o l o u r sf o re a c hc o u n t r mt h u st h ea b o v e - m e n t i o n e dz c h o o s a b i l i t y p r o b l e ma s k sa b o u tt h ec h o o s a b i l i t yo fs i m p l ep l a n a rg r a p h s g r a p h c h o o s a b i l i t yi s ag e n e r a l i z a t i o no fg r a p h - c o l o r a b i l i t y ，t h ec o n c e p to f l i s tc o l o u r i n g sa n dc h o o s a b i l i t yw a si n t r o d u c e di nt h es e v e n t i e si n d e p e n d e n t l yb y v i z i n g 1 】a n de r d 6 s ，r u b i na n dt a y l o r 2 t h e yg a v et h ed e f i n i t i o n sa n df i r s t r e s u l t sa n dm e n t i o n e dal o to fi n t e r e s t i n go p e np r o b l e m s s i n c et h eb e g i n n i n go f t h en i n e t i e sl a s tc e n t u r yal o to fm a t h e m a t i c i a nh a v eb e c o m ei n t c r e s t e di nt h e s e p r o b l e m sa n ds t a r t e di n v e s t i g a t i o n si ns e v e r a ld i r e c t i o n s i n1 9 7 9 ，e r d s s ，r u b i na n dt a y l o r 2 1c o n j e c t u r e d ： 1 e v e r yp l a n a rg r a p hi s 5 - c h o o s a b l ea n d 2 t h e r ea r ep l a n a rg r a p h sw h i c ha r en o n - 4 c h o o s a b l e t h et w oe o n j e c t u r e sw e r ep r o v e di n1 9 9 3 i nt h ef o l l o w i n gw ec o n s i d e ras p e c i a lr e s t r i c t i o no nt h ev e r t e xd e g r e e so fa g r a p ha n d i t sc o n s e q u e n c e sf o rt h ec h o o s a b i l i t y l e tu sr e c a l lt h ed e f i n i t i o no ft h e d - d e g e n e r a t e t h es i m p l e s tp a r t i c u l a rc a s e sa r et h ee d g e l e s sg r a p h s ( d = 0 ) a n d t h ef o r e s t s ( d = 1 ) t u z a ，v o i g tg i v e nt h ef o l l o w i n gt h e o r e m ： t h e o r m ea t u z a ，v o i g t ； 2 8 e v e r yd - d e g e n e r a t eg r a p hgi s ( ( d + 1 ) m ，m ) 一 c h o o s a b l e o ra l lm 1 f o re x a m p l e ，t h ep l a n a rg r a p h sa r e5 - d e g e n e r a t eb e c a u s eo fe u l e r sf o r m u l a a n dt h e r e f o r ee v e r yp l a n a rg r a p hi s6 - c h o o s a b l e n z a ，v o j g t f 2 8 ja l s os h o w nt h a t e v e r yc h o r d a lg r a p hgi s ( x ( a ) m ，m ) 一c h o o s a b l ef o r 以lm 1 o nt h et w oc o n j e c t u r e s ，t h o m a s s e ng a v eav e r yi n t e r e s t i n gp r o o fo ft h ef i r s t c o n j e c t u r eu s i n gn e i t h e re u l e r sf o r m u l an o rr e - c o l o u r i n go fa l r e a d yc o l o u r e dv e r - t i c e s t h e o r m eb t h o m a s s e n ；【3 e v e r yp l a n a rg r a p hi s5 - e h o o s a b l e e x a m p l e so fp l a n eg r a p h sw h i c ha r en o t4 - c h o o s a b l ew e r e 舀m e nb yv o i g ti n 【4 v e r i f i e dt h es e c o n do ft h e s ec o n j e c t u r e s 5 o nt h e5 - c h o o s a b l e ，r s k x e k o v s k i 3 6 e x t e n dt h et h e o r e mab ys h o w i n gt h a t “ik 5 一m i n o r f r e eg r a p l l sa r e5 - c h o o s a b l e o n4 - c h o o s a b l e ，l a me ta l 6 ，7 p r o v e dt h ef o l l o w i n gt h e o r e m ： t h e o r m ec f l a m ，x u ，l i ua n ds h i u ； 6 ，7 l e tg b ea p l a n eg r a p h 口gi sc k - f r e e 如rs o m e 3 ，4 ，5 ，6 ，t h e ni ti s ( 4 m ，m ) - c h o o s a b l e 拍ra l lm n x u 8 ，9 p r o v e dt h a te a c hg r a p h e m b e d d e do ns u r f a c e so f p o s i t i v ec h a r a c t e r i s t i c a n di nw h i c hn 0t w ot r i a n g l e ss h a r eac o m m o nv e r t e xi s4 - c h o o s a b l e w a n ga n d l i b t 0 1 ，i n d e p e n d e n t l y , p r o v e d t h a te a c h p l a n eg r a p hw i t h o u tt w ot r i a n g l e ss h a r i n g c o m m o nv e r t e xi s4 一c h o o s a b l e ， w ew i l lf u r t h e rd i s c u s s3 - e h o o s a b i l i t yi nc h a p t e r2 o n 2 - c h o o s a b l e ，e r d s s ，r u b i na n dt a l o r 2 】c h a r a c t e r i z e da l lg r a p h sw h i c ha r e 2 一c h o o s a b l e t h e o r m e d e r d 6 s ，r u b i na n dt a y t o r ；1 2 1 ac o n n e c t e dg r a p hg i s2 - c h o o s a b l e 铲 a n do n l y 矿琥ec o r eo f gb e l o n g st o d = k 1 ，c 2 r ，e 2 j 2 p ：r 2 ，p 1 ) o nn o n k - c h o o s a b l eg r a p h s t h ef i r s t e x a m p l eo fan o n 4 一c h o o s a b l ep l a n a r g r a p hw a sg i v ei n 4 1 ，t h e r e b yp r o v i n gt h ea b o v em e n t i o n e ds e c o n dc o n j e c t u r e t h i sg r a p hh a s2 3 8v e r t i c e sa n dc h r o m t i cn u m b e r4 t h ee x i s t e n c eo ft h i sg r a p hs h o w st h a tt h ed i f i e r e n c eb e t w e e nt h em a x i m u m c h o i c en u m b e ro fp l a n a ra n dt h em a x i m u mc h r o m a t i cn u m b e ro fp l a n a rg r a p h s i sa tl e a s t1 t h i sf a c ti sn o t e w o r t h yb e c a u s ef o ra 1 1o t h e rs u r f a c e se x c e p tt h e s p h e r et h em a x i m u m c h o i c en u m b e ro fe m b e d d a b l eg r a p h se q u a l st h em a x i m u m c h r o m a t i cn u m b e ro fe m b e d d a b i eg r a p h s ( 1 2 9 7 ) ， a n o t h e rp r o b l e mw h i c ha p p e a r e dw a st h eq u e s t i o nw h e t h e re v e r y 七一c o l o r a b l e p l a n a rg r a p hi s ( 女+ 1 ) 一c h o o s a b l e t h i sp r o b l e m i sm e n t i o n e d b yt h o m a s s e n ( 【1 5 】) a n da l s ob yj e u s e na n d t o f t 2 9 1 t h ef i r s ta n s w e r t ot h i sq u e s t i o ni sh i d d e ni nt h e p a p e r o fg u t n e r 3 0 1w h o g a v ea ne x a m p l e o fap l a n a rg r a p hw i t h7 5v e r t i c e sw h i c h i sn o t4 一c l l o o s a b l e g u t h e rd i dn o tc o n s i d e rt h ec h r o m a t i en u m b e ro ft h i sg r a p h w h i c hi so b v i o u s l y3 ，t h n st h e r ea r ek - c o l o u r a b l ep l a n a rg r a p h sw h i c ha r en o t + 1 ) 一c h o o s a b l e v o i g t a n d w i r t h 5 】a l s op r e s e n t e d a3 - c o l o r a b l en o n - 4 - c h o o s a b l e p l a n eg r a p h 1 3m a i nr e s u l t s t h e o r m e1l e tgb eap l a n a rg r a p ho fg i r t hn o tl e s st h a n4 t h e ngi s3 一 c h o o s a b l e 矿gc o n t a i n sn o5 一a n d6 - c i r c u i t s t h e o r m e2l e tgb ea p l a