外可平面圖的2，139;染色問題

1、南京師范大學碩士學位論文外可平面圖的（2，1）-染色問題姓名：郭海榮申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：許寶剛20080201A b s t r a c tA b s t r a c tA g r a p hG = ( y ( G ) ，E ( G ) ) i s ( 七，d ) ·- c o l o r a b l e ，i f i t sv e r t i c e sc a n b ec o l -o r e

2、d w i t h k c o l o r s i ns u c ha w a y t h a t e a c h v e r t e x i sa d j a c e n t t O a tm o s td v e r t i c e s w i t ht h es a m e c o l o r a si t s e l f ．A n d e a c h s u c h c o l o r i n g i sc a l l e da

3、 ( k ，d ) 。- c o l o r i n g o fG ．W ed e n o t e t h ec h r o m a t i cn u m b e r o fG b yx a ( G ) = m i n { 忌lG i s ( 忌，d ) ·- c o l o r a b l e } ．A g r a p hG i sc a l l e do u t e r p l a n a ri f i t c a n b

4、 ce m b e d d e d i n a p l a n es u c ht h a ta l lv e r t i c e sl i eO l lt h eb o u n d a r yo ft h eu n b o u n d e da r e a ．T h e p l a n e C a l lb ed i v i d e d i n t os e v e r a lc o n n e c t e da r e a sb y

5、t h e e d g e so f G ，t h e n t h ec l o s u r eo f e a c ha r e ai s “ c a l l e daf a c eo f t h eg r a p h ．I np a r t i c u l a r , t h e u n b o u n d e d a r e a i sc a l l e dt h eo u t s i d e f a c e ．A g r a p

6、hG i sc a l l e dm a x i m a l o u t e r p l a n a l ：g r a p h ，i f i tc a n b e e m b e d d e d i na p l a n e S O t h a ta l lo fi t sf a c e s b u t t h eo u t s i d e o n e a r et r i a n g l e s ．·O n i m p r

7、o p e r c o l o r i n g s o f o u t e r p l a n a r g r a p h s ，L ．J ．C o w e n ，R ．H ．C o w e na n d D ．R ．W o o d a l lp r o v e d t h a te v e r yo u t e r p l a n a rg r a p h i s ( 2 ，2 ) ·- c o l o r a b l e

8、；a n dt l l e ya l s of o u n d a no u t c r p l a n a r g r a p h w h i c h i sn o t ( 2 ，1 ) ‘- c o l o r a b l e 【6 】．I nt h i sp a p e r , w ed i s c u s st h e ( 2 ，1 ) ‘- c o l o r i n go f o u t e r p l a n a rg r

9、 a p h sw i t h o u tt r i a n g l e sa n d w i t ho n l yt r i a n g l e s ( i ．e ．m a x i m a lo u t e r p l a n a rg r a p h s ) ．W c p r o v e t h a te v e r y t r i a n g l e - f r e eo u t 呻l a n a rg r a p hi s (

10、2 ，1 ) ·- c o l o r a b l e ；M e a n w h i l e ，w ep r o p o s es o m ed e s c r i p t i o n so n ( 2 ，1 ) * - c o l o r i n go f o u t e r p l a n a rg r a p h s w i t ha n dw i t h o u t c u tv e r t i c e s ，r e