（基础数学专业论文）图的染色问题及其推广.pdf

摘要 摘要 本文主要研究有关有限无向简单图的染色相关的一些问题 图g 的一个正常顶点染色是指k 种颜色1 ，2 ，k 对于g 的各顶点 的一个分配，使得任意两个相邻的顶点分配以不同颜色若图g 有一个 正常克点染色，那么就称图g 是南一点可染色的图g 的色数是指g 有一 个正常k 顶点染色的数k 的最小值，用x ( a ) 表示 图g 的一个顶点色列表l 是一个颜色集合簇，它指定g 的每个顶点 秽一个颜色集合三( u ) 对于一个给定的色列表厶若g 有一个正常的顶点 染色丌，使得对每一个顶点v y ( g ) ，有7 r ( v ) l ( u ) ，则称g 为己顶点可 染的或者称7 r 是g 的一个l 染色若对每一个满足l l ( u ) l 忌，v v ( a ) 的厶g 都是l 点可染的，则称g 是惫点列表可染的，简称g 是k 列表可 染的，或称为忌可选的g 的顶点列表色数( g ) 是使得g 是忌可选择 的最小的非负整数k 图的列表染色是图的染色的一个推广，列表染色的概念首先由 v i z i n g 【6 8 】和e r d 6 s 等人【3 2 】在2 0 世纪7 0 年代提出1 9 7 9 年，e r d s s ， r u b i n 和t a y l o r 【3 2 】提出了下面的猜想 猜想1 2 1 ( e r d 6 s ，r u b i na n dt a y l o r 3 2 ) ( 1 ) 每个平面图是5 - 可选色 的；( 2 ) 存在平面图不是4 可选色的 从2 0 世纪9 0 年代以来，大量的学者和专家对图的选色问题进行了 研究，并得出了一系列成果上述的猜想分别由t h o m a s s e n 于1 9 9 4 年【6 5 】 中及v o i g t 于1 9 9 5 年【6 9 】中予以解决所有的2 一可选色的平面图已由 e r d 6 s ，r u b i n 和t a y l o r 在【3 2 】中进行了特征化的刻画g u t n e r 于1 9 9 6 年 在文献【3 6 】中证明这类着色问题是n p 完全的所以众多学者转向寻找 摘要 一个图是3 可选色或4 可选色的充分条件我们在论文中讨论了类似的 问题，进一步得到了如下的结果 定理2 2 1 若g 是一个无5 ，6 和7 一圈的平面图，如果g 中任意两个 三角形的距离至少为3 ，则g 是3 可选色的 定理2 2 2 若g 是一个无5 ，6 和8 一圈的平面图，如果g 中任意两个 三角形的距离至少为2 ，则g 是3 可选色的 定理2 2 3 若g 是一个无4 ，5 ，7 一和1 0 圈的轮胎图，则g 是3 可选 色的 假若染色7 r 是图g 的正常项点染色，并且对于g 中的任何一个圈子 图c 都用到至少3 种颜色，那么我们称染色7 r 是g 的一个无圈染色图 g 的无圈色数x 口( g ) 就是使得g 是无圈七一可染的最小的非负整数忍 对于一个给定的色列表l 若g 有一个正常的无圈染色7 r ，使得对每 一个顶点u y ( g ) ，都有7 r ( v ) l ( u ) ，则称g 是无圈l 一可染的或者称7 r 是g 的一个无圈l 染色。若对每一个满足i l ( u ) l k ，v v ( a ) 的色列 表厶g 都是无圈l 可染的，则称g 是无圈庇列表可染的，简称g 是无圈 尼可选的g 的无圈列表色数x i ( g ) 是使得g 是无圈七一列表可染的最小 的非负整数忌 在第3 章中，我们讨论了无指定圈的平面图的无圈选色问题，记 一个弦七圈为一个带弦的凫圈我们给出了下述结果，此结果改进了 m o n t a s s i e r 等人在( 5 5 ，2 0 0 6 ) 及( 【5 9 1 ，2 0 0 7 ) 中的一些结果 定理3 2 1 若g 是一个无4 和弦6 圈的平面图，则g 是无圈5 可选 色的 定理3 2 2 若g 是一个无4 和6 圈的轮胎图，则g 是无圈5 可选色 的 推论3 2 1 若g 是一个无4 和5 一圈，或无4 和6 一圈，或无3 和4 一圈 摘要 的平面图，则g 是无圈5 可选色的 每个分支均为路的图称为线性森林，图g 的一个亡一线性染色是指t 种颜色1 ，2 ，t 对于g 的各条边的一个分配，使得( y ( g ) ，- 1 ( 口) ) 是一 个线性森林，其中1 o t 亡图g 的线性荫度l a ( g ) 定义为最小的整数t 使得g 有一个线性染色 本文第4 章对非负欧拉特征值图的亡线性染色进行了讨论首先给出 了一个特殊非负特征值图类的结构结论，运用此结论，讨论了此类图当最 大度较小时的线性荫度值 定理4 2 1 若g 是一个无4 和相交3 一圈的非负特征值图，如果 a ( g ) 5 ，则l a ( a ) 3 论文的最后我们列出一些关于图的染色的可进一步研究的问题 关键词：图，列表染色，选色，无圈选色，线性染色，非负欧拉特征值 a b s t r a c t a b s t r a c t i nt h i sd i s s e r t a t i o n ，w ei n v e s t i g a t em a i n l ys o m ec o l o r i n gp r o b l e m so fu n d i - r e c t e df i n i t es i m p l eg r a p h s ak - c o l o r i n go fag r a p hgi sam a p p i n g7 rf r o mv ( c 1t ot h es e t 1 ，2 ，尼) s u c ht h a t7 r ( x ) 丌( 可) f o ra n ya d j a c e n tv e r t i c e sz a n dy t h e g r a p hg i sk - c o l o r a b l ei fi th a sak - c o l o r i n g t h ec h r o m a t i cn u m b e rx ( a ) o fg i sd e f i n e da st h el e a s ti n t e g e rks u c ht h a tg i sk - c o l o r a b l e ac o l o rl i s tl = | l ( u ) ：v y i saf a m i l yo f c o l o rs e t sa s s i g n e dt oe a c h v e r t e xo fg a nl c o l o r i n go fgi sa na s s i g n m e n to fc o l o r st oe a c hv e r t e xu v f r o ml ( v ) s u c ht 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 a g r a p hgi sc a l l e dk - c h o o s a b l e ( o rk - l i s tc o l o r a b l e ) i fg a d m i t sa nl 。 c o l o r i n gf o re a c hc o l o rl i s tl w i t hkc o l o r si ne a c hl i s t t h ec h o i c en u m b e ro f g 。d e n o t e db yx z ( a ) ，i st h em i n i m u m 尼s u c ht h a tg i sk - c h o o s a b l e g r a p h c h o o s a b i l i t yi sag 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 t o fl i s tc o l o r i n ga 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 y b yv i z i n g 6 8 a n de r d 6 s ，r u b i na n dt a y l o r 3 2 1 n e yg a v e t h ed e f i n i t i o n sa n d f i r s tr 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 i n19 7 9 ，e r d 6 s ， r u b i na n dt a y l o r 【3 2 】p 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 2 1 ( e r d r s ，r u b i na n dt a y l o r 【3 2 1 ) ( 1 ) e v e r yp l a n a rg r a p h i s 5 一c h o o s a b l e ；( 2 ) t h e r ea y 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 s i n c et h eb e g i n n i n go ft h en i n e t i e sl a s tc e n t u r yal o to fg r a p ht h e o r i s t sh a v e b e c o m ei n t e r e s t e di nt h e s ep 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 o nc o n j e c t u r e1 2 1 ，t h o m a s s e n 【6 5 1g a v eav e r ye l e g a n tp r o o fo ft h e 一1 1 a b s t r a c t f i r s tc 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 r i n go fa l r e a d yc o l o r e d v e r t i c e s 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 eg i v e nb y v o i g ti n 【6 9 】v e r i f y i n gt h el a t t e rp a r to ft h ec o n j e c t u r e a l l2 - c h o o s a b l eg r a p h sw e r ec h a r a c t e r i z e dc o m p l e t e l yi n 3 2 i tr e m a i n s o p e nt od e t e r m i n ew h e t h e rag i v e np l a n eg r a p hi s3 一o r4 - c h o o s a b l e i n 【3 6 ， g u t n e rp r o v e dt h a tt h e s ep r o b l e m sa l en p c o m p l e t e t h e r e f o r e ，m a n ya u t h o r s t r i e dt of i n ds u f f i c i e n tc o n d i t i o n sf o rap l a n eg r a p ht ob e3 - o r4 - c h o o s a b l e w e d i s c u s st h i st y p eo fp r o b l e m si nt h i sd i s s e r t a t i o n ，a c t u a l l y , w eg i v et h ef o l l o w i n g r e s u l t so n3 - c h o o s a b i l i t yo fg r a p h s t h e o r e m2 2 1 e v e r yp l a n e g r a p hw i t h o u t5 - ，6 一a n d7 - c y c l e s ，a n dw i t h o u t t r i a n g l e so fd i s t a n c el e s st h a n3i s3 - c h o o s a b l e t h e o r e m2 2 2e v e r yp l a n e g r a p hw i t h o u t5 一，6 - a n d8 - c y c l e s ，a n dw i t h o u t t r i a n g l e so fd i s t a n c el e s st h a n2i s3 - c h o o s a b l e t h e o r e m2 2 3 e v e r yt o r o i d a lg r a p hw i t h o u t4 一，5 一，7 一a n d10 - c y c l e si s 3 c h o o s a b l e a p r o p e rv e r t e xc o l o r i n go fag r a p hi sa c y c l i ci ft h e r ei sn o b i c o l o r e dc y c l e i ng t h ea c y c l i cc h r o m a t i cn u m b e r , d e n o t e db y ( g ) ，o fag r a p hg i st h e s m a l l e s ti n t e g e rks u c ht h a tgh a sa na c y c l i cc o l o r i n gu s i n g 尼c o l o r s a g r a p hg i sa c y c l i c a l l yl - l i s tc o l o r a b l ei ff o rag i v e nl i s ta s s i g n m e n tl = l ( u ) ：秒y ) ，i ft h e r ee x i s t sap r o p e ra c y c l i cc o l o r i n g 丌o fg s u c ht h a t 7 r ( v ) l ( v ) f o ra l lv y ( g ) i fgi sa c y c l i c a l l yl - l i s tc o l o r a b l ef o ra n yl i s ta s s i g n m e n tlw i t hl l ( u ) i k f o ra l lv v ，gi sc a l l e da c y c l i c a l l yk - c h o o s a b l e t h ea c y c l i cc h o i c en u m b e r o fg ，) ( ：( g ) ，i st h es m a l l e s ti n t e g e r 足s u c ht h a tgi sa c y c l i c a l l yk - c h o o s a b l e i nc h a p t e r3 ，w ew i l lc o n c e n t r a t eo nt h ea c y c l i cc h o o s a b i l i t yo fp l a n e 一1 1 1 a d s t r a c t g r a p h sw i t h o u tp r e s c r i b e dc o n f i g u r a t i o n s ac h o r d a lk - c y c l ei sak - c y c l ew i t ha c h o r d a c t u a l l y ，w ep r o v et h ef o l l o w i n gr e s u l t s ，a n dt h ec o r o l l a r yg e n e r a l i z e d t h er e s u l t si n 5 5 】a n dac o r o l l a r yi n 5 9 t h e o r e m3 2 1 e v e r yp l a n eg r a p hw i t hn e i t h e r4 - c y c l e sn o rc h o r d a l6 。 c y c l e si sa c y c l i c a l l y5 - c h o o s a b l e t h e o r e m3 2 2e v e r yt o r o i d a lg r a p hw i t h o u t4 一a n d6 - c y c l e si sa c y c l i c a l l y 5 c h o o s a b l e c o r o l l a r y3 2 ie v e r yp l a n eg r a p hw i t h o u t4 一a n d5 - ，o r4 。a n d6 ，o r3 a n d4 - c y c l e si sa c y c l i c a l l y5 - c h o o s a b l e al i n e a rf o r e s ti sag r a p hi nw h i c he a c hc o m p o n e n ti sap a t h am a p 西 f r o me ( c ) t o 1 ，2 ，3 ，t ) i sc a l l e dat - l i n e a rc o l o r i n gi f ( y ( g ) ，- i ( 口) ) i s al i n e a rf o r e s tf o r1 o l t t h el i n e a ra r b o r i c i t yl a ( g ) o fag r a p hg d e f i n e d b yh a r a r y 【3 7 i st h em i n i m u m n u m b e rtf o rw h i c hgh a sat - l i n e a rc o l o r i n g w ec a l lag r a p ho fn o n n e g a t i v ec h a r a c t e r i s t i ca nn c - g r a p h l e t9d e n o t e t h es e to fn c - g r a p h sw i t h o u t4 - c y c l e sa n di n t e r s e c t i n gt r i a n g l e s i nc h a p t e r4 ，w es t u d yt h el i n e a ra r b o r i c i t yo fac e r t a i nt y p eo fg r a p h sw i t h n o n n e g a t i v ec h a r a c t e r i s t i c f i r s t ，w ec o n s i d e rt h es t r u c t u r a lp r o p e r t i e so fg r a p h s i n9 ，a p p l y i n gt h e s ep r o p e r t i e s ，w ed i s c u s st h el i n e a ra r b o r i c i t yo fg r a p h si n9 w i t hs m a l lm a x i m u m d e g r e e t h e o r e m4 2 1l e tgb eag r a p hw i t ha ( g ) 5i n9 t h e nl a ( g ) 3 i nt h ee n do ft h i sd i s s e r t a t i o n ，w el i s ts o m ep r o b l e m sf o rf u r t h e rr e s e a r c h e s o nt h i st o p i c k e y w o r d s ：g r a p h s ，l i s tc o l o r i n g ，c h o o s a b i l i t y ，a c y c l i cc h o o s a b i l i t y ，l i n e a r c o l o r i n g ，n o n n e g a t i v ec h a r a c t e r i s t i c i v c h a p t e r1 i 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 s t h r o u g h o u tt h i sw o r kw ec o n s i d e rg r a p h so n l yf i n i t e ，u n d i r e c t e d ，l o o p l e s s ， a n dw i t h o u tm 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 wt h a t o fb o n d ya n dm u r t y 【1 4 g = ( ve ，f ) d e n o t e sap l a n eg r a p h ，w i t hv ，ea n d fb e i n gt h es e to fv e r t i c e s ，e d g e sa n df a c e so fgr e s p e c t i v e l y i fe = u vi sa ne d g eo fg ，t h e nei ss a i dt o j o i nv e r t i c e sua n du ，ua n du a r e s a i dt ob ea d j a c e n ta n du ( r e s p e c t i v e l yv ) i ss a i dt ob ei n c i d e n tw i t ht h ee d g ee t w o e d g e sea n d e 7a r ea d j a c e n ti ft h e ya r ei 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 x 乱i nag r a p hg ，d e n o t e da sa t ( u ) ，i st h en u m b e ro f e d g e si ng i n c i d e n tw i t hu t h em a x i m u m d e g r e eo fa l lv e r t i c e si ng i sd e n o t e d b y ( g ) ，a n dt h em i n i m u md e g r e eo fa l lv e r t i c e si ng i sd e n o t e db y6 ( g ) l e t g ( u ) ( o rs i m p l y ( u ) ) d e n o t e t h es e to fn e i g h b o r so fav e r t e xui ng ag r a p hhi sas u b g r a p ho ft h eg r a p hg ( w r i t t e nhcg ) i fv ( h ) i sa s u b s e to fv ( a ) a n de ( h ) i sas u b s e to fe ( g ) s u p p o s ev 1cv ( a ) a n d i s n o n e m p t y t h es u b g r a p ho fg w 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 e s e to ft h o s ee d g e so fgt h a th a v eb o t he n d si nv li sc a l l e dt h es u b g r a p ho fg i n d u c e db yv 1 as u b g r a p hh i sa s p a n n i n gs u b g r a p ho fg i fv ( h ) = y ( g ) t w oc y c l e 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 n b 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 ea d j a c e n ti ft h e y h a v ea tl e a s to n ec o m m o nb 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 y o faf a c el 。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 o1 af a c ei s i n c i d e n tw i t ha l lv e r t i c e sa n de d g e so ni t sb o u n d a r y6 ( ，) 一一 生：2 ：! ! ：! = 2 1 ：! i 2 2 一一一一 ak - v e r t e xi sav e r t e xo fd e g r e ek ，a n dak + 一( o rk - ) v e r t e xi sav e r t e xo f d e g r e ea tl e a s t ( o ra tm o s t ) k t h ed e g r e eo faf a c efo fg ，d e n o t e db yd c ( f ) ， i st h en u m b e ro 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 d g ( 厂) = k ，t h e nfi sc a l l e dak - f a c e ak + 一( o r 七一) f a c e ，i sa f a c eo fd e g r e ea t l e a s t ( o ra tm o s t ) k ak - c y c l ei sac y c l eo nkv e r t i c e s ac h o r d a lk - c y c l ei sa k - c y c l ew i t hac h o r d t h ev e r t e xs e to fac y c l ecw i l la l s ob ed e n o t e db yc t h es e to fa l lk c y c l e so fg i sd e n o t e db y 瓯( g ) ag r a p hi sc a l l e d 仇一f r e ei f 瓯( g ) = t h e g i r t ho fg i st h el e n g t ho fas h o r t e s tc y c l eo fg at o m 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 t b o u n d a r y ) 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 h 2 - c e l le m b e d a b l eo nt h et o m s f o rat o r o i d a lg r a p hg ，w es t i l lu s egt od e n o t e a2 - c e l le m b e d d i n go fgo nt o m s a p l a n a rg r a p hi sag r a p ht h a tc a nb ee m b e d d e di nt h ep l a n e ，i e ，i tc a nb e d r a w no nt h ep l a n ei ns u c haw a yt h a ti t se d g e si n t e r s e c to n l ya tt h e i re n d p o i n t s a p l a n a rg r a p ha l r e a d yd r a w ni nt h ep l a n ew i t h o u te d g ei n t e r s e c t i o n si sc a l l e da p l a n eg r a p h l e tgb eap l a n eg r a p h f o r z v ( c ) uf ( g ) ，w eu s e 兄( z ) t od e n o t et h e s e to fa l lk f a c e st h a ta r ei n c i d e n to ra d j a c e n tt oz ，a n dk ( z ) t od e n o t et h es e t o fa l lk - v e r t i c e st h a ta r ei n c i d e n to ra d j a c e n tt oz f o rf f ( g ) ，w ew r i t ef = u l u 2 仳竹】i fu l ，u 2 ，u na r et h eb o u n d a r y v e r t i c e so ffi nt h ec l o c k w i s eo ra n t i c l o c k w i s eo r d e r a nn f a c e 心l u 2 u 3 u n 】 i sc a l l e da n ( m 1 ，m 2 ，m 3 ，m n ) - f a c ei fd ( u i ) = m if o ri = 1 ，2 ，3 ，佗 t h ed i s t a n c eb e t w e e nt w ov e r t i c e sza n dy ，d e n o t e db yd i s t ( x ，秒) ，i st h e l e n g t ho fas h o r t e s tp a t hc o n n e c t i n gt h e mi ng t h ed i s t a n c eb e t w e e nt w o t r i a n g l e sta n dri s d e f i n e dt ob et h ev a l u em i n d i s t ( x ，v ) l x v ( t ) a n d 一2 一 y y ( r ) ak - c o l o r i n go fg i sam a p p i n g 丌f r o mv ( a ) t ot h es e t 1 ，2 ，尼) s u c h t h a t7 r ( x ) 7 r ( 可) f o ra n ya d j a c e n tv e r t i c e sza n dy ag r a p hgi sk - c o l o r a b l e i fi th a sak - c o l o r i n g t h ec h r o m a t i cn u m b e rx ( g ) o fgi sd e f i n e da st h el e a s t i n t e g e rks u c ht h a tg i sk - c o l o r a b l e al i n e a rf o r e s ti sag r a p hi nw h i c he a c hc o m p o n e n ti sap a t h am a p 西 f r o me ( g ) t o 1 ，2 ，3 ，t ) i sc a l l e dat - l i n e a rc o l o r i n gi f ( y ( g ) ，- 1 ( q ) ) i s al i n e a rf o r e s tf o r1 口t t h el i n e a ra r b o r i c i t yl a ( g ) o fag r a p hgi st h e m i n i m u mn u m b e rtf o rw h i c hgh a sat - l i n e a rc o l o r i n g 1 2c h o o s a b i l i t yo fg r a p h s ac o l o rl i s tl = l ( u ) ：v y ) i saf a m i l yo f c o l o rs e t sa s s i g n e dt oe a c h v e r t e xo fg a nl c o l o r i n go fgi sa na s s i g n m e n to fc o l o r st oe a c hv e r t e xv v f r o ml ( v ) s u c ht 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 e ( o rk - l i s tc o l o r a b l e ) i fga d m i t sa nl c o l o r i n gf o re a c hc o l o rl i s tlw i t hkc o l o r si ne a c hl i s t t h ec h o i c en u m b e ro f g ，d e n o t e db yx t ( c ) ，i st h em i n i m u m ks u c ht h a tgi sk - c h o o s a b l e g r a p h c h o o s a b i l i t yi sag 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 t o f l i s tc o l o 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 6 8 】a n de r d 6 s ，r u b i na n dt a y l o r 3 2 t h e yg a v et h ed e f i n i t i o n sa n d f 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 fg r a p ht h e o r i s t sh a v eb e c o m ei n t e 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 n19 7 9 ，e r d 6 s ，r u b i na n dt a y l o r 【3 2 】p 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 2 1 ( e r d 6 s ，r u b i na n dt a y l o r 【3 2 】) ( 1 ) e v e r yp l a n a rg r a p hi s 一3 一 c h a p t e r1i n t r o d u c t i o n 5 - c h o o s a b l e ；( 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 s o m er e s u l t so ni n t e r e s t i n gp r o b l e m si nt h i sf i e l de n c o u r a g e di t sd e v e l o p - m e n t c e r t a i n l yo n eo ft h e s er e s u l t s i st h ea n s w e rt ot h ec o n j e c t u r eo fe r d 6 s ，r u - b i na n dt a y l o rc o n c e r n i n gt h ec h o o s a b i l i t yo fp l a n eg r a p h s i n19 9 4t h o m a s s e n g a v eav e r ye l e g a n tp r o o fo ft h ef i r s tc 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 a n o rr e c o l o r i n go fa l r e a d yc o l o r e dv e r t i c e s t h e o r e m1 2 1 ( t h o m a s s e n 【6 5 】) e v e r yp l a n a rg r a p hi s5 - c 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 eg i v e nb yv o i g t i n 【6 9 】v e r i f y i n gt h el a t t e rp a r to ft h ec o n j e c t u r e ag r a p hgi s ( f ，夕) 一c h o o s a b l ei fg i v e na r b i t r a r yc o l o rs e t sa ( v ) w i t h i a ( u ) i = f ( v ) t oe a c h o fv y ( g ) ，w ec a nc h o o s es u b s e t sb ( v ) a ( v ) w i t h j b ( u ) i = g ( v ) s u c h t h a tb ( u ) nb ( v ) = dw h e n e v e r 牡u e ( g ) s u p p o s eg i s ( ，9 ) - c h o o s a b l e ，w h e r efa