（運籌學(xué)與控制論專業(yè)論文）關(guān)于圖的點可區(qū)別染色問題.pdf

關(guān)于圖的點可區(qū)別染色問題 摘要 圖的染色理論是圖論研究的重要理論之一近幾年來，各類染色問題也被相 繼提出，圖的點可區(qū)別染色問題以及鄰點可區(qū)別染色問題是圖的染色理論中的 一種推廣本文主要研究了圖的點可區(qū)別邊染色及鄰點可區(qū)別全染色問題 論文分為三章，在第一章中主要是對本學(xué)位論文所涉及到的問題、背景、定 義及點可區(qū)別染色問題的研究現(xiàn)狀進(jìn)行一個綜述 第二章主要研究了一些圖的點可區(qū)別邊染色的問題1 9 9 3 年，a c b u r r i s h e 和r h s c h e l p 提出了圖的點可區(qū)別邊染色的概念和猜想，并得到了一些結(jié)果 h a l i n 圖一直以來是學(xué)者們較為關(guān)注的一類圖本章主要研究了3 正則h a l i n 圖 和a ( c ) 4 的h a l i n 圖的點可區(qū)別邊染色問題，并得到了星、扇、輪等聯(lián)圖即 & v & 、rvr 、v 眠的點可區(qū)別均勻邊色數(shù) 第三章研究了關(guān)于圖的鄰點可區(qū)別全染色問題2 0 0 2 年，張忠輔教授根據(jù)計 算機(jī)科學(xué)、信息科學(xué)、網(wǎng)絡(luò)等實際問題，在點可區(qū)別邊染色的基礎(chǔ)上提出了鄰 點可區(qū)別邊染色、鄰點可區(qū)別全染色的概念和猜想本章主要探討了( g ) = 7 的2 連通外平面圖的鄰點可區(qū)別全染色問題 關(guān)鍵詞：點可區(qū)別染色；均勻邊染色；全染色；h a l i n l 羽 t h ep r o b l e mo fv e r t e xd i s t i n g u l s h i n g c o l o r i n g o fg r a p h s a b s t r a c t t h ec o l o r i n gt h e o r yo fg r a p hi so n eo ft h ei m p o r t a n tt h e o r yi ng r a p h s r e c e n t l y , m a n yk i n d so fc o l o r i n gp r o b l e m sa r ep r e s e n t e d ，s u c ha st h ev e r t e xd i s t i n g u i s h i n ge d g e c o l o r i n ga n da d j a c e n tv e r t e xd i s t i n g u i s h i n gc o l o r i n ga r ea l lt h ee x t e n s i o no fc o l o r i n g t h e o r y i nt h i sp a p e rw ed e a lw i t hs o m eg r a p h si nv e r t e xd i s t i n g u i s h i n ge d g ec o l o r i n g o ra d ja c e n tv e r t e xd i s t i n g u i s h i n gc o l o r i n gp r o b l e m sb yu s i n gt h ei n d u c t i o nm e t h o d t h i st h e s i sc o n s i s t so ft h r e ec h a p t e r s i nt h ef i r s tc h a p t e r , w ei n t r o d u c es o m e p r o b l e m s 、b a c k g r o u n d sa n dt h ed e f i n i t i o no fv e r t e xd i s t i n g u i s h i n gc o l o r i n g i nt h es e c o n dc h a p t e r , w em a i n l yd e a lw i t i lt h ev e r t e xd i s t i n g u i s h i n ge d g ec o l o r - i n gp r o b l e m i n19 9 3 ，a c b u r r i s h ea n dr h s c h e l pp r e s e n t e dt h en e wd e f i n i t i o na n d c o n j e c t u r eo fv e r t 固ad i s t i n g u i s h i n gc o l o r i n g ，a n do b t a i n e ds o m er e s u l t s i nt h i sc h 印- t e r , w ei n v e s t i g a t et h ev e r t e xd i s t i n g u i s h i n ge d g ec o l o r i n gi n3 - r e g u l a rh a l i ng r a p ha n d h a l i ng r a p hv v i t h ( g ) 4 a l s o ，w eo b t a i nt h ev e r t e xd i s t i n g u i s h i n ge q u i t a b l ee d g e c h r o m a t i cn u m b e ro f & v & 、rvr 、w nv i nt h et h i r dc h a p t e r , w es t u d yt h ea d j a c e n tv e r t e xd i s t i n g u i s h i n gt o t a lc o l o r i n g p r o b l e m b a s e do nt h et h e o r yo f v e r t e xd i s t i n g u i s h i n gc o l o r i n g ，p r o f e s s o rz h a n gz h o n g f u p r e s e n t e d t h en e wd e f i n i t i o na n dc o r l j e c t u r eo fa d j a c e n tv e r t e xd i s t i n g u i s h i n gc o l o r i n g i nt h i sc h a p t e r , w ei n v e s t i g a t et h ea d j a c e n tv e r t e xd i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e r o n2 - c o n n e c t e do u t e rp l a n eg r a p hw i t ha ( g ) = 7 k e yw o r d s ：v e r t e xd i s t i n g u i s h i n gc o l o r i n g ；e q u i t a b l ee d g ec o l o r i n g ；t o t a lc o l o r i n g ；h a l i ng r a p h l l 浙江! j 幣范大學(xué)學(xué)位論文獨創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得 的研究成果論文中除了特別加以標(biāo)注和致謝的地方外，不包含其他人或其他機(jī) 構(gòu)已經(jīng)發(fā)表或撰寫過的研究成果其他同志對本研究的啟發(fā)和所做的貢獻(xiàn)均已在 論文中作了明確的聲明并表示了謝意本人完全意識到本聲明的法律結(jié)果由本人 承擔(dān) 名：象嘴 吼叫年月節(jié)日 學(xué)位論文使用授權(quán)聲明 名緣任”魏f 。7 焱午日p 伊 浙江師范大學(xué)學(xué)位論文誠信承諾書 我承諾自覺遵守浙江師范大學(xué)研究生學(xué)術(shù)道德規(guī)范管理條例我的學(xué)位 論文中凡引用他人已經(jīng)發(fā)表或未發(fā)表的成果、數(shù)據(jù)、觀點等，均已明確注明并詳 細(xì)列出有關(guān)文獻(xiàn)的名稱、作者、年份、刊物名稱和出版文獻(xiàn)的出版機(jī)構(gòu)、出版 地和版次等內(nèi)容論文中未注明的內(nèi)容為本人的研究成果 如有違反，本人接受處罰并承擔(dān)一切責(zé)任 何彳 船似 、，e口 蜘 師 究 聊 教 1 1 有關(guān)概念 1緒論 本文所考慮的圖g 都是有限、無向、簡單圖分別用y ( g ) 、e ( g ) 、( g ) 、 d g ( u ) 和( u ) 表示圖g 的頂點集、邊集、最大度、頂點 的度與和頂點u 相 鄰的點的集合在不引起混淆的情況下，分別簡記為y 、e 、d ( v ) 和( 口) 在 圖g 中與頂點讓相鄰的頂點的全體叫做u 的鄰域，記作n e ( u ) ，稱i g ( ) i 為點 亂的度數(shù)，記作如( “) 如果圖g 的所有頂點度數(shù)都等于d 則稱圖g 是d 正則的 為方便，將度數(shù)為k 的頂點叫做七點，度數(shù)為0 的點稱為孤立點，度數(shù)為l 的點稱為 懸掛點或葉點，與懸掛點相關(guān)聯(lián)的邊叫做懸掛邊 對于圖g = ( ke ) 和圖g = ( v ，e ) ，若有y ke e ，則稱圖g 是圖g 的一個子圖進(jìn)一步，如果g 7 包含所有形如x y e ( g ) ，x ，y v7 的 邊，則稱g 為g 的一個導(dǎo)出子圖，并記作g = a i r 1 用仫表示圖g 的所 有最大度頂點組成的集合，則g 【仫l 表示由所有最大度頂點導(dǎo)出的g 的子圖， e ( g v a l ) = ele = u v e ( g ) ，u ，u 仫) 于是e ( g 【壇1 ) = d 表示g 中沒有兩 個相鄰的最大度頂點，e ( a v a 】) d 即表示g 中有兩個相鄰的最大度頂點 稱圖h = ( v uv ，eue ) 為圖g 與g 7 的并，記作gug 對于y y ( g ) ， 從g 中刪去y 中頂點及與其中的頂點相關(guān)聯(lián)的邊后得到的圖記作g 【y y l 或g y7 ；對于u ，u y ( g ) ，u u e ( g ) ，在g 中連接點u ，u 后得到的圖記作 g + 仳口 若y y 中的任何兩個頂點都不相鄰，則稱y 為圖g 的一個點獨立 集若e e 中的任何兩條邊都不相鄰、則稱e 為g 的一個邊獨立集或匹配 若g 的一個匹配e 包含g 的所有頂點，則稱e 為完美匹配 若從連通圖g 中任意刪去七一1 個點后g 仍連通，則稱圖g 是七連 通的對于x y ( g ) ，若g x 不連通，則稱x 是g 的一個點割集，當(dāng) l l 緒論 g 一 z ) 不連通，點x 稱為g 的一個割點不含圈的圖叫做森林；連通的 無圈圖叫做樹對于佗+ 1 階的圖s ，若v ( s ) = x o ，x l ，z n ) ，e ( s ) = x o x l ，x o x 2 ，x o x 。) ，則稱s 為禮階星，記為島對于佗+ 1 階的圖f ，若 v ( p ) = z o ，x l ，x 。 ，e ( r ) = x o x l ，x o x 2 ，x o x t l ；x l x 2 ，x 2 x 3 ，x n - 1 x n ， 則稱f 為佗階扇，記為r 對于禮+ l 階的圖w ，若v ( w ) = 執(zhí)，x l ，z 。 ， e ( w ) = x o x l ，x o x 2 ，z o z 。；x l x 2 ，x 2 x 3 ，x n - l x 他，x n x l ，則稱為t i 階輪， 記為帆 對于圖g = ( k e ) ，若y 中任何兩個頂點都相鄰，則稱g 是完全圖或團(tuán)若 y 可剖分成r 個類，w ，其中r 是一個大于等于2 的正整數(shù)，使得k 是 g 的獨立集，則稱g 為r 部圖若卜部圖的每個頂點與其所在部以外的點都相鄰， 則稱g 為完全r 部圖 若能將圖g 嵌入在一個平面上，使得它的邊僅在端點處相交，則稱g 是一個 可平面化圖，圖g 在平面上的一個嵌入叫做平面圖g 文中未加說明的術(shù)語和記 號可參見文【4 】 1 。2 關(guān)于圖的點可區(qū)別染色研究綜述 圖論在現(xiàn)代科學(xué)技術(shù)中有著廣泛的應(yīng)用，如：社會學(xué)、計算機(jī)科學(xué)、信 息科學(xué)、密碼學(xué)、d n a 的基因譜的確定和計數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中 的優(yōu)化方法等都廣泛地應(yīng)用了圖論及其算法關(guān)于圖的染色問題，是圖論 研究的主要內(nèi)容之一，并且近年來圖的染色問題得到了廣泛的研究和應(yīng) 用，新概念、新方法不斷的出現(xiàn)，是當(dāng)前非?；钴S的學(xué)科問題1 而圖的點 可區(qū)別染色問題是眾多類型中用不同方式對圖進(jìn)行標(biāo)號的一個特殊問題 1 9 9 3 年a c b u r r i s h e 和r h s c h e l p 提出了圖的點可區(qū)別邊染色的概念和猜想此 后包括a c b u m s h e 在內(nèi)，r h s c h e l p ，p n b a l i s t e r , b b o l l o d s 等人在文獻(xiàn)閉中做了 進(jìn)步的探討2 0 0 2 年，張忠輔教授【3j 根據(jù)計算機(jī)科學(xué)、信息科學(xué)、網(wǎng)絡(luò)等實際 問題，在點可區(qū)別邊染色的基礎(chǔ)上提出了鄰點可區(qū)別邊染色、鄰點可區(qū)別全染色 2 l 緒論 的概念和猜想本文所考慮的圖均為連通、有限、無向的簡單圖 對于給定的簡單圖g 和正整數(shù)k ，若存在映射廠：e ( g ) 一 1 ，2 ，3 ，七 滿足任意相鄰的邊e ，e 有f ( e ) f ( e ) ，則稱，為g 的一個正常邊染色，簡記為 k p e co fg 且稱 x7 ( g ) = m i n kik p e co fg 為g 的邊色數(shù)【4 1 若，是g 的一個k p e c ，且滿足v u ，u y ( g ) ，u u ，其中c ( u ) c ( v ) ， 則稱，為g 的點可區(qū)別邊染色，簡記為k v d e co fg ，而 x 0 ( g ) = m i n kl k v d e co fg ， 稱為g 的點可區(qū)別邊色數(shù)f5 1 ，其中 c ( u ) = f ( u v ) iu y e ( g ) 對簡單圖g ，6 ( g ) ，a ( a ) 分別是g 的最小度和最大度，扎i 表示g 中度數(shù)為i 的點數(shù)，( 二) 表示n 個中取m 個的組合數(shù)，則稱 肛e g ，= m a x t m t n t zi ( ：) 扎i ，6 c g ，t c g ， 為g 的組合度 6 1 由組合度及點可區(qū)別邊染色定義，不難得到 x 幺( g ) 肛( g ) 3 ( 1 1 ) 1 緒論 設(shè)廠是g 的一個k v d e c ，且滿足 e i l l 馬i f 1 則稱，為g 的點可區(qū)別均勻邊染色，簡記為七一v d e e co fg ，而稱 x 贏( g ) = m i n ki 七一v d e e co fg ) 為g 的點可區(qū)別均勻邊色數(shù)【6 1 ，其中 e i = eif ( e ) = 啦 為解決網(wǎng)絡(luò)權(quán)的分配等問題，b u m s 、b a z g a n 等人先后提出點可區(qū)別邊染色 問題，得n t 相應(yīng)的結(jié)果，在有關(guān)結(jié)論的前提下提如下猜想 猜想1 1 7 1 對于i v ( g ) i 3 的連通圖g ，有 u ( o ) x 幺( g ) u ( c ) + 1 張忠輔等人得到了一些聯(lián)圖的點可區(qū)別均勻邊色數(shù)，并且在此基礎(chǔ)上提出了 以下猜想 猜想2 1 3 1 對l v ( a ) l 3 的簡單圖g ，有 ( 1 ) 肛( g ) x 幺( g ) 肛( g ) + l ； ( 2 ) x 巍( g ) = x t ( g ) 設(shè)g ( ke ) 是階數(shù)至少為2 的簡單連通圖，k 為正整數(shù)，是v ( c ) ue ( c ) 到 1 ，2 ，七) 的映射，對任意u v ( a ) i d c i ( u ) = ，( u ) u f ( u v ) lu u e ( g ) 如果滿足 ( 1 ) 對任意u u ，v w e ( g ) ，“叫有，( “u ) f ( v w ) 4 1 緒論 ( 2 ) 對任意姐u e ( a ) 有，( u ) ，( ) ，( 札) ，( u u ) ，( u ) f ( u v ) ，則稱 廠為 g 的k 正常全染色進(jìn)一步，如果還滿足 ( 3 ) 對任意亂釘e ( g ) ，有qu ) q ( u ) ，那么稱，為g 的七一鄰點可區(qū)別全染 色，簡記為k a v d t c ，稱 x 。t ( g ) = m i n klk a v d t co fg 為g 的鄰點可區(qū)別全色數(shù)| 8 】 張忠輔等人研究了路、圈、完全圖、完全二部圖、星、扇和輪的鄰點可區(qū) 別全染色，得到了相應(yīng)圖的鄰點可區(qū)別全色數(shù)，并根據(jù)對這些圖的研究結(jié)果，提出 了以下猜想 猜想3 1 8 】 對階數(shù)不小于2 的連通圖g ，有x 。( g ) 5z x ( c ) + 3 圍繞以上的猜想，許多學(xué)者對點可區(qū)別染色問題做了一系列的探討和研究， 得到了以下一些結(jié)論 定理1 1 9 1 若圖g 是k 可染的且無孤立邊，則有x ：( g ) ( g ) + o ( 1 0 9k ) ； 定理1 2 【1 0 1若扎階圖g 是無孤立邊且至多有一個孤立點，則有x 幺( g ) s 定理1 3 【l l l 1 2 1 對n 2 ，有x ( rvr ) ： n + 3 ，2 他6 ； l 禮+ 4 ，禮7 對禮3 ，有x k c rvc k ，= 三+ 4 ，n n = 4 6 ； 對扎3 ，有x ：，d e ( gvg ) = 扎+ 4 ； 對幾23 ，cx ；如( rvg ) = 3 t = 八i 氍 n 5 l 軌 ，-lj-i_一， 1 緒論 定理1 41 8 對任意的簡單圖g ，有x 以( g ) a ( c ) + l ；若圖g 有兩個相 鄰最大度點，則x t ( c ) a ( c ) + 2 ；若g 有k 個連通分支g 1 ，g 2 ，g 詹，且 i y ( g i ) l 2 ( i = 1 ，2 ，七) ，則有x t ( o ) = m a x x n ( g 1 ) ，x 。t ( g 2 ) ，x 。( g 七) ； r 設(shè)表示禮階完全圖m 3 ) ，則有x 。( ) ： 禮+ 1 扎= o ( r o o d 2 ) ； 【卅2 ，n = l ( m o d 2 ) 除此之外，還有以下一些結(jié)果： ( 1 ) 0 3 1 若g 是最大度為3 的簡單圖，則有x n ( g ) s6 r ( 2 ) 1 11 1 1 1 4 1 令g 是一個圈g ，則有x 口( g ) ： 4 扎= 3 ； 【5 ，扎4 若a ( c ) = 3 ，則有x 。t ( g ) = 5 ； r 若( g ) _ 4 則有( g ) ： 5 以g 蹦) - 眈 【6 ，e ( c i v i l ) o ， 若( g ) _ 5 ，則有( 卟 6 鄺( g 盼1 ) 劃； 【7 ，e ( c i v i l ) o ， ( 3 ) 1 5 1 設(shè)g 是( g ) ：6 的2 - 連通夕卜平面圖，貝 j 有x “g ) ： 7 瑚( g 盼| ) 劃； i 8 ，e ( g 【仫】) o 6 2 圖的點可區(qū)別邊染色 2 1h a l i n 圖的點可區(qū)別邊染色 本節(jié)考慮h a l i n 圖假設(shè)g 是一個3 連通平面圖，如果將其外面r 邊界上所 有的邊刪去后( 蜀上所有頂點的度為3 ) ，g 得到一棵生成樹t ，則稱g 是一個 h a i n 圖f o 成為g 的外面( 其它的成為內(nèi)面) ，v ( 媧) 成為外面上的點，也叫外點 ( 其余的統(tǒng)稱為內(nèi)點) 若g 是一個點集合為y ( g ) ，邊集合為e ( g ) 的h a l i n 圖令，是g 的一 個邊染色，且c tv ) = ，( u u ) iu u e ( g ) 記為與點可關(guān)聯(lián)的邊所染的顏色 集合，記t d = 禮d ( g ) 為g 中點度為d 的點的個數(shù)，其中t f ( g ) d ( g ) ，用 n o ( c ) = i v ( f o ) f 記為外點的個數(shù)過去，許多學(xué)者研究了h a l i n 圖的邊染色【1 6 l ， 列表染色【l7 1 ，近年來有一些學(xué)者開始考慮h a l i n 圖的鄰點可區(qū)別邊染色【l8 1 引理2 1 1 9 1g 是一個3 正則h a l i n 圖且g w 3 ，那么g 包含結(jié)構(gòu)n 或b ( 如 圖2 1 ) ，2 圖2 1 引理2 2 1 9 l 圖g 是一個h a l i n 圖，一1 是階為p 的輪，則有 ( f ) 外面上的頂點的度數(shù)均為3 ；并且任意兩個面至多只有一條公共邊 ( i i ) 若g 箬一1 ，那么g 中至少有兩個內(nèi)點；且總是存在一個內(nèi)點刪，使得它 僅與一個內(nèi)點相鄰； 7 2 圖的點可區(qū)別邊染色 ( i i i ) 若g 嚳一1 ，叫是( i ) 中的一個項點，設(shè)n ( w ) = 札，v l ，u 2 ， ，其中 u 是唯一的一個與w 相鄰的內(nèi)點，u l ，v 2 ，v 知是與叫相鄰的外點，且x 是與y l 相鄰的外點，x o ，z 1 是x 其余的兩個鄰點；y 是與訊相鄰的外點，y o ，y l 是其余的 兩個鄰點考慮 h 1 = g 一 1 ，v 2 ，v k + z 叫，可叫 ； h 2 = g 一 仉，可件l ，吩 + u 一1 + 1 ) ，2 i j 6 根據(jù)數(shù)學(xué)歸納，任意一個 6 n o ( h ) n o ( a ) 的3 一正則h a l i n 圖h 有一個n o ( h ) v d e c ， 由引理2 2 得，g 包含圖2 1 所示的結(jié)構(gòu)a 或b ( a ) 若g 含結(jié)構(gòu)a ，假設(shè)u l ，“1 ，u 5 ，u 3 ，t j 3 都是g 中的外點( 否則可以取出有此 特征的一組點) 令 h = g u l ，u s + y l u 4 ，u 3 u 4 顯然，v l ，“3 ，u 4 都在日的外面上，并且日是一個3 正則h a l i n 圖，n o ( 日) = n o ( o ) - a ，因此日有一個( n o ( a ) 一1 ) - v d e c ，記色集為c = 1 ，2 ，3 ，孔o(hù) ( g ) 一 l 不失一般性，設(shè) f ( 3 1 l z 4 ) = 1 ，f ( u 3 u 4 ) = 2 ，f ( u 2 u 4 ) = 3 9 區(qū) 2 圖的點可區(qū)別邊染色 若未說明，假設(shè)g 中邊的顏色與日中所對應(yīng)的邊的顏色一致下面我們利用 一個新的顏色n o ( c ) 來完成對g 中的邊的染色首先，令9 ( v l u l ) = 1 ，g ( u 3 u 5 ) = 2 ，g ( u l u 4 ) = 3 其次，令g ( u 2 1 2 4 ) = 夕( u l u 5 ) = n o ( c ) 最后，分三種情況對邊u 4 u 5 進(jìn)行染色 情況1f ( u 2 u 3 1 = 1 根據(jù)點可區(qū)別邊染色的定義可知f ( u 3 v 3 ) 隹q ( “4 ) ，設(shè)f ( u 3 v 3 ) = 口( 口簪 l ，2 ，3 ) ) ，令g ( u 4 u 5 ) = o t ，則此時的夕是g 的一個n o ( g ) 一v d e c 情況2f ( u 2 u 3 ) 1 但f ( u 3 v 3 ) = 1 顯然可知，f ( u 2 u 3 ) 垡q ( “4 ) ，不妨設(shè)f ( u 2 u 3 ) = p ( 口聾 1 ，2 ，3 ) 若f ( u 2 v 2 ) 2 ，可設(shè)g ( u 4 u 5 ) = p 否則，重染g ( u ：u 3 ) = 3 ，令g ( u 4 u 5 ) = p 因此任意兩個不同 的點含有不同的色集合 情況3f ( u 2 u 3 ) 1 且f ( u 3 v 3 ) 1 因為f ( u 2 u 3 ) 岳c f ( u 4 ) ，f ( u 3 v 3 ) 隹 1 ，2 ，f ( u 2 u 3 ) ，令f ( u 2 u 3 ) = ，y ( ，y 簪 l ，2 ，3 ) ) 若，( u 3 1 ) 3 ) = 3 ，顯然，f ( u 2 v 2 ) 2 ，則可令f ( u 4 u 5 ) = 7 若y ( , 吐3 v 3 ) 3 ， 不失一般性，設(shè)，( 蝴忱) = q ( a 隹 1 ，2 ，3 ，y ) ，再令g ( u 4 u 5 ) = o t ( b ) 若g 包含結(jié)構(gòu)b ，假設(shè)釘l ，u 1 ，u 6 ，u 7 ，1 1 3 是g 外面上的點令 h = g 一 “1 ，訛 + v l u 4 ，u 4 u t 那么u 1 ，批，u 7 是日外面上的點，則日是一個3 一正則h a l i n 圖，且珊( h ) = n o ( g ) - 1 ，因此日有一個( n o ( c ) 一1 ) - v d e cf ，令色集合為c = 1 ，2 ，3 ，n o ( c ) 一1 不妨設(shè) f ( y l u 4 ) = 1 ，廠( u 4 讓7 ) = 2 ，f ( u ：u 4 ) = 3 若未說明，假設(shè)g 中邊的顏色與日中所對應(yīng)的邊的顏色一致類似地，下面我們 利用一個新的顏色n o ( c ) 來完成對g 中的邊的染色先令g ( v l u l ) = 1 ，g ( u 6 u 7 ) = 1 0 2 圖的點可區(qū)別邊染色 2 ，g ( u 1 u 4 ) = 3 ，然后設(shè)9 ( u l u 6 ) = g ( u 2 u 4 ) = n o ( v ) 最后，邊u 4 u 6 的染法如下 若2 隹 f ( u 2 v 2 ) ，( u 2 u 5 ) ，則令9 ( u 4 u 6 ) = 。，x ，( 亂2 u 2 ) ：f ( u 2 u s ) 1 若2 ，( u 2 可2 ) ，廠( u 2 u 5 ) ) ，由于i c i 6 ，則可令g ( u 4 u 6 ) = x ，z c 1 ，3 ，n o ( g ) ，( u 2 u 2 ) ，( 牡2 u 5 ) ) 因此，9 是g 的一個點可區(qū)別邊染色，故有 x 0 ( g ) n o ( g ) 定理2 2 若g 是一個h a l i n 圖且a ( g ) 24 ，則x 0 ( g ) sn o ( g ) 證明若g = 則由引理2 3 ，有x i ( c ) n o ( c ) 若g 嚳，對n o ( g ) 進(jìn)行數(shù)學(xué)歸納 若n o ( g ) = 5 ，因為g 是一個h a l i n 圖，所以當(dāng)刪去r 上所有邊時，g 得到一棵 生成樹t ，有n t ( t ) = n o ( g ) = 5 因為 a ( t ) i 1 , 1 ( t ) = ( d 一2 ) r i d ( t ) + 2 d - - - 3 則n 3 ( t ) = m ( t ) = 1 ，扎d ( t ) = 0 ，d 5 ，此時滿足條件的圖只有一個，易得 x ：( g ) = 5 ( 如圖2 3 ) n o i g ) = 5 圖2 3n o ( g 1 = 5 9 j h a h n 圖 假設(shè)定理對于n o ( g ) n o ( e ) ，( g ) 4 的h a l i n 圖日均成立，下面證明對 于g ，定理同樣成立假設(shè)是所有滿足引理2 2 中條件( i i ) 的w ( 只與一個內(nèi)點相 鄰) 的頂點集合，并讓w 是w 中最小的一個頂點，令n ( w ) = u ，v l ，v 2 ，譏， 此處的u 是唯一的一個與w 相鄰的內(nèi)點， 1 ，釘2 ，仇是與t t ) 相鄰的外點，設(shè)z 1 1 2 圖的點可區(qū)別邊染色 是與u 1 相鄰的外點，x o ，x 1 是z 的另外兩個鄰點；y 是與u k 相鄰的外點，y o ，y l 是 y 的兩個鄰點 情況1d ( w ) = 3 ： 令n ( w ) = “，v 1 ，u 2 ) 考慮 h = g 一 1 ，v 2 + 叫。，加可， 則由引理2 2 ，h 仍然是一個h a l i n 圖且a ( h ) = ( g ) ，n o ( h ) = n o ( v ) 一1 根據(jù) 歸納假設(shè)，日有一個( n o ( v ) - 1 ) - v d e cf ，令色集合c = 【l ，2 ，n o ( c ) 一1 ) 情況1 1f ( w y ) c f ( z ) ，f ( w x ) c f ( 可) 不失一般性，假設(shè) f ( w x ) = f ( y y o ) = 1 ，f ( w y ) = f ( x x o ) = 2 ， 則f ( y y l ) 聾c f ( ) ，y ( x x l ) 圣c f ( w ) 且y ( y y l ) f ( x x l ) 令f ( x x l ) = 4 ，廠( 可1 ) = 5 ，則無論邊z 1 染什么顏色，c f ( x ) c f ( ) 總是成 立令g ( v l w ) = g ( v 2 y ) = n o ( g ) ，且g ( v l x ) = l ，g ( v l v 2 ) = 4 ，g ( 7 3 2 w ) = 2 情況1 2f ( w y ) q ) ，f ( w x ) q ( ) ( 對于情況f ( w y ) 隹c ， ) ，y ( w x ) q ( 可) ，證明方法類似，略) 假設(shè) i ( w x ) = 1 ，f ( w y ) = f ( x x o ) = 2 ，i ( x z l ) = 4 因為f ( w x ) 聾c f 白) ，所以可令g ( v l w ) = 1 ，g ( v l v 2 ) = 3 ，g ( v 2 w ) = 2 ，再用新的顏 色n o ( g ) 去染邊 u l z ，v 2 y 情況1 3i ( w v ) 隹c i ( z ) ，f ( w x ) 隹q ( ) 不失一般性，令，( 叫z ) = 1 ，i ( w y ) = 2 ，( u 叫) = 3 ，則1 萑q ( 可) 那么可令 g ( v l x ) = 1 ，g ( v l v 2 ) = 4 ，9 ( v 2 w ) = 2 ，并利用新的顏色n o ( g ) 去染邊v 1 w ，v 2 y 1 2 2 圖的點可區(qū)別邊染色 情況2d ( w 1 = 4 ： 令n ( w ) = u ，v l ，1 ) 2 ，v 3 考慮圖 日= g 一 u 1 ，v 2 ，v 3 + w x ，w y ， 則由引理2 2 可知，h 仍然是一個h a l i n 圖，且n ( ) ( 日) = n o ( a ) 一2 若( h ) ( g ) ，那么日是一個3 - 正則h a l i n 圖，根據(jù)定理2 1 ，x ：( h ) s 呦( 日) + 1 = n o ( g ) 一1 因此，h 有一個( m ( g ) 一1 ) 一v d e cf ，令其色集合 為c = l ，2 ，扎o ( g ) 一l 為完成對g 的染色，我們可以利用一個新的顏 色n o ( g ) 令 f ( w x ) = 1 ，f ( w y ) = 2 ，f ( u w ) = 3 顯然，我們可以假設(shè)g ( v l z ) = g ( v 3 w ) = l ，9 ( v 3 b ) = 9 ( v 2 w ) = 2 ，g ( v l v 2 ) = 3 ，并令 g ( v 2 v 3 ) = g ( v l w ) = n o ( c ) 若a ( h ) = ( g ) ，由歸納假設(shè)可知，h 有一個( n o ( g ) 一2 ) 一v d e cf 令其 色集合為c = 1 ，2 ，n o ( a ) 一2 ，在完成g 的染色過程中，我們可以利用兩個 新的顏色螄( g ) 一l ，禮o ( g ) 由于d ( u ) 4 比d ( u ) = 4 時的證明更簡單，所以不妨 設(shè)d ( u 1 = 4 令 f ( w x ) = 1 ，f ( w y ) = 2 ，廠( u 叫) = 3 顯然，可令9 ( v l z ) = g ( v 3 w ) = 1 ，9 ( v 3 y ) = g ( v l w ) = 2 ，g ( v l v 2 ) = 3 ，并且令 g ( v 2 v 3 ) = 伽( g ) 一1 ，9 ( v 2 w ) = n o ( g ) 情況3d ( w ) 5 ： 令n ( w ) = u ，v l ，y 2 ，v a ( 。) 一1 考慮 h = g 一 u 1 ，1 ) 2 ，v d ( 。) 一1 + w x ，w y ， 若a ( h ) ( g ) ，染法類似于情況2 2 圖的點可區(qū)別邊染色 若a ( h ) = ( g ) ，那么由引理2 2 可知，h 仍然是一個h a l i n 圖且n o ( h ) = n o ( g ) 一d ( w ) + 2 因為( 日) = a ( c ) 且d ( w ) 25 ，由叫的選取顯然有n o ( c ) d ( 叫) + 4 根據(jù)歸納假設(shè)和引理2 3 ，h 有一個( n o ( c ) 一d ( w ) + 2 ) 一v d e c ，令 其色集合為c = t 1 ，2 ，n o ( g ) 一d ( w ) + 2 類似地，對于g 的染色，我們可以用另外的d ( w ) 一2 種顏色 n o ( c ) 一d ( w ) + 3 ，m ( g ) 一d ( w ) + 4 ，珈( g ) 去完成染色令 f ( w z ) = 1 ，l ( w y ) = 2 ，( u 叫) = 3 首先，令g ( v l z ) = l ，g ( v a ( 。卜l y ) = 2 其次，對任意的i t l ，2 ，d ( w ) 一2 ) ， 令g ( v i 仇+ 1 ) = i + 2 最后，令g ( v i w ) = n o ( g ) 一d ) + i + l ，i 2 ，3 ，d ) 一 1 ，g ( v l w ) = 4 其他e ( g ) 中未說明的邊的染色與h 中對應(yīng)的邊相同，因此，g 有一個 佗o ( g ) 一v d e cg ，其色集合為 1 ，2 ，n 0 ( g ) ，所以定理成立 2 2 星、扇、輪聯(lián)圖的點可區(qū)別均勻邊染色 設(shè)島、r 、帆分別是幾+ 1 階的星、扇、輪圖在下面的一些運算中，若其 結(jié)果大于2 孔+ 2 ，則取模2 億+ 2 x 乙c & v & ，= 2 禮：2 ，：三： 證明設(shè)兩個星圖的點集和邊集分別為v o ，口1 ， ， 晶，t ，i ，穢： ； 如仇ii = 1 ，2 ，禮，( v o v ：i1 = 1 ，2 ，禮) 則當(dāng)禮2 時，v & 的度 1 4 2 圖的點可區(qū)別邊染色 序列為( n + 2 ，n + 2 ，n + 2 ，2 n + 1 ，2 n + 1 ) ，由度序列易計算 鵬v 啦k2 ，萎 情況1 他= 1 ：s 1vs 1 = k 4 ，由【4 】知結(jié)論為真 情況2t t = 2 ：島v = bv 島，由【6 】知結(jié)論為真 情況3t , 3 ：由( 1 1 ) 式，x 贏( v & ) 2 n 十2 所以我們僅需證明v & 存在( 2 n + 2 ) 一v d e e ce p - - i 設(shè)c = 1 ，2 ，2 n + 2 ，蠆( 叫) = c c ( 叫) ，w y ( 島v ) 情況3 1n 蘭o ( m o d 2 ) 定義f 為：，( 珈) = 扎+ 2 ；，( 嵋口號) = 1 ；f ( v o v 詈) = 2 ；，( 珈穢等+ 1 ) = 扎+ 3 ； 廠( 瑤仇) ： + 詈+ 2 ， 1 ，詈一1 ) ； li + n + 2 ，i 考+ 1 ，幾) ，( 嵋t ，：) = f ( v o v i ) = i + 1 ， i 1 ，詈 ； i 十詈十2 ，i 詈+ 1 ，佗， i + 摯+ 3 ，i l ，鷥一1 ) ； i + 1 ， i + 2 ，死 ，c 珈口：，= ；二；3 ，；蘭；：l ：j _ ：， ，c 優(yōu)巧，= ：；二；：；：歹蘭雩：【：j ? n 對f ，有蠆( 珈) = 1 ；蠆( u 6 ) = 號+ 2 】- ； ，-_i，1li-，_j l l 一一 2 圖的點可區(qū)別邊染色 二= r _ 一一 時： 時 c ( u 暑) = 1 ，2 ) u + 2 ，咒+ 1 ) u 摯+ 3 ，2 n + 2 1 ； c ( u 爭 1 ) = 1 ) u 考+ 3 ，孔+ 3 ) u 摯+ 3 ，2 n + 2 1 ； c ( v h = i + 2 ，i + 詈+ 2 ) u ( i + 扎+ 3 ，i + 摯+ 3 ) ，當(dāng)i 1 ，詈一1 c ( u i ) = l + 1 ，i + 墨+ l iu i + n + 2 ，i + 警+ 2 ) ，當(dāng)i 1 【營+ 2 ，禮， c ( u ：) = 1 ) 一，i + 2 ) u i + 3 ，2 n + 2 ，當(dāng)t l 一，呈_ 時； c ( 口：) = i 一爹+ 2 ，i + 號+ 3 ) ，當(dāng)i 考+ 1 ，禮 時 從而在染色f - f ，& v & 中任意兩個頂點有不同的色集，故，是& v & 的 一個( 2 n + 2 ) 一v d e c 又 e i 墨+ 1 ， i 1 ，詈+ 2 ) u 扎+ 2 ，3 n 2 + 2 ； 詈+ 2 ， i ( 考+ 3 ，n + 1 ) u 警+ 3 ，2 n + 2 故，是& v & 的一個( 2 n + 2 ) 一v d e e c 倩況3 , 2 n 三l ( m o d 2 ) 當(dāng)n = 5 時，定義，如下表2 1 所示： 此時易知，是一個1 2 正常邊染色，且島v 民中任意兩個頂點有不同的色集， 故廠是& v 島的一個1 2 一v d e c 又 ， 馴： 3 6 ，8 k l 4 ， 其它 、 故，是& v 的一個1 2 一v d e e c 1 6 2 圖的點可區(qū)別邊染色 表2 1 f v o 6 v lv 2v 31 3 4) 5 1 2l2345 v o 硝 1 2 23456 u i 674591 08 口5 7891 0l l1 2l 嵋 891 2l l5l7 囈 91 0l l 1 2l23 囈 1 0l l76234 當(dāng)n = 7 時，定義，如下表2 - 2 所示： 耙2 f t j 0 嵋 v lv 2v 3u 4v 57 3 61 3 7 51 6l21 0678 v o 嵋 5 789l1 41 51 6 u ： 32l l1 21 31 41 51 6l t ，； 4 31 21 31 41 51 6l2 嵋 941 31 41 51 6l23 釘i l l1 03456281 5 囈 1 2l 14567891 0 u ： 1 31 2 5 6 7 391 0l l u ； 1 41 367891 0 l l1 2 此時易知f 是一個1 6 正常邊染色，且s rv 函中任意兩個頂點有不同的色集， 故，是島v 島的一個1 6 一v d e c 又 叫鞭 2 圖的點可區(qū)別邊染色 故廠是島v 島的一個1 6 一v d e e c 當(dāng)禮9 時，定義廠為：，( 6 ) = 學(xué)；廠( u 6 u 學(xué)) = 1 ；廠( 如鈔- - 。) = 禮+ 2 ；f ( v o u 字) = 1 ；f ( v o u 孚) = 2 ；，( 如u 字) = 扎+ 3 ；，( u l u ：) = 學(xué)； f ( v j v i ) = ，( 諾u ：) ，( 如) = f ( v o v i ) f ( v i v t n ) = i + 下n + l + 2 ， i + 幾+ 2 ， i - 4 - 1 ， i + 半+ 2 ， i l ，孚】； i 字，扎) i 1 ，孚) ； i _ 【丁n + l ，孔 i + 2 ， i 1 ，字 ； i + 半+ 3 ，i l n + 2 l ，佗 i + 學(xué)+ 4 ，i l ，學(xué) ； i + 1 ， i 學(xué)，n 】i i ，i 2 ，孚 ； i + 半+ l ，i 丁n + l ，n ，