圖的D（2）-點可區(qū)別及點可區(qū)別正常邊染色.pdf

1、密級——一莎』侖蠢予箍史學碩士學位論文圖的D ( 2 ) ．點可區(qū)別及點可區(qū)別正常邊染色劉利群導師姓名職稱：陵攔墾煎援專業(yè)名稱： 廛屆數堂 研究方向：圖迨丞墓廑鍾論文答辯日期：2 Q Q Z 生量旦 學位授予日期：至Q Q 2 生魚旦答辯委員會主席：評 閱 人：二O o 七年五月A b s t r a c tL e tG W , E 1 b eac o n n e c tg r a p hw i t ho r d e ra tl e a

2、 s t3 , aa n dp a r e p o s i t i v ei n t e g e r s ，a n d f i sam a p p i n g f r o mE ( G ) t o { 1 ，2 ，?，a ) ，I f ，i s a p r o p e re d g e c o l o r i n g ，a n df o ra n yp o s i t i v e 矽a n d a n yt ‘，口∈y ( G ) ，0

3、 < d ( n ，t ，) S ∥，w eh a v ec ( ∞≠G ( t ，) ，t h e nf i sc a l l e d口一D ( 國一v e r t e xd i s t i n g u i s h i n gp r o p e r e d g ec o l o r i n go fg r a p h a ( a —D ( 所一V D P E C o fG i nb r i e f ) a n dt h en u

4、 m b e r 磊- v d ( G ) = m i n { a l G h a s a 口一D ( f 1 ) 一V D P E C } i s c a l l e dn —D ( 口' ) - v e r t e xd i s t i n g u i s h i n ge d g e c h r o m a t i cn u m b e r o fg r a p h G ．I t i so b v i o u s t h

5、a tx ；一謝( G ) e x i s t sf o r a n y g r a p hG w i t hJ y ( G ) I ≥3 ．A n dx ：一v d ( G ) =x 0 ( G ) i s c a l l e da d j a c e n ts t r o n ge d g e c h r o m a t i cn u m b e r o fg r a p hG ；x 二一謝( G ) = f A G )i sc a

6、 l l e dv e r t e xd i s t i n g u i s h i n ge d g ec h r o m a t i cn u m b e ro fg r a p hG ，w h e r eD d e n o t e st h ed i a m e t e ro f c o n n e c t e dg r a p h G ．I n t h i s p a p e rs o m ep r o b l e m so f

7、D ( 2 ) ．v e r t e x d i s t i n g u i s h i n gp r o p e re d g ec o l o r i n ga n dv e r t e xd i s t i n g _ 1 f i s h i n gp r o p e re d g ec o l o r i n ga x ed i s c u s s e d ．T h e r ea r ef o u rp a r t s ：I n

8、t h ef i r s tp a r t ，s o m ed e f i n i t i o n s ，t h e o r e m sa n d S Oo na r eg i v i n g ．I n t h es e c o n d p a r t ，D ( 2 ) - v e r t e xd i s t i n g u i s h i n gp r o p e re d g ec o l o r i n go fe x t e

9、n d e dM y c i e l s k ig r a p h so f s o m eg r a p h s a r ed i s c u s s e d ，a n dt h eD ( 2 ) 一v e r t e xd i s t i n g u i s h i n gp r o p e re d g ec h r o m a t i c n u m b e r s a r e o b t a i n e d ．I nt h e

10、 t h i r d p a r t ，w i t ha p p l y i n g L o v S 舊z L o c a l L e m m a - G e n e r a l L o c a l L e m m a ，a n u p p e rb o u n d sf o r D ( 2 ) 一v e r t e x d i s t i n g u i s h i n gp r o p e r e d g ec h r o m a

11、t i cn u m b e ri s d i s c u s s e da n do b t a i n e d ．A tl a s t ，t h ev e r t e x - d i s t i n g u i s h i n gp r o p e re d g ec h r o m a t i cn u m b e ro f 磁V 甄，P m V％( m 2 5 ) a n d ％v ‰( m ≥4 ) a r e a l s o

12、d i s c u s s e d ．K e y w o r d s ：V e r t e xd i s t i n g u i s h i n gp r o p e r e d g e c o l o r i n g ；V e r t e xd i s t i n g u i s h i n gp r o p e re d g ec h r o m a t i cn m n b e r ；D ( 2 ) 一v e r t e x d

13、i s t i n g u i s h i n gp r o p e re d g ec o l o r i n g ；D ( 2 ) 一v e r t e xd i s -t i n g u i s h i n gp r o p e re d g ec h r o m a t i c m l m h e r ；E x t e n d e dM y c i e l s k ig r a p h s ；J o i ng r a p h s