【摘要】：圖的頂點(diǎn)著色是圖論中的重要研究專題,在實(shí)際生活中有著極其廣泛的應(yīng)用.諸如學(xué)生選課,四色問(wèn)題,會(huì)議安排,中繼站分配特別是計(jì)算機(jī)網(wǎng)絡(luò)方面許多問(wèn)題都能轉(zhuǎn)化為頂點(diǎn)著色問(wèn)題.圖的r-多彩著色是正常頂點(diǎn)著色,且滿足每個(gè)度數(shù)為d(v)的頂點(diǎn)其鄰點(diǎn)的顏色數(shù)至少為min{d(v),r}.它把圖的正常著色(1-多彩著色),動(dòng)態(tài)著色(2-多彩著色),平方著色(△-多彩著色)都包括在內(nèi),是一種非常有意義的新著色.確定一個(gè)圖能否進(jìn)行r-多彩著色的最小顏色數(shù)也就是r-多彩色數(shù),是該專題研究的首要任務(wù).圈和路是最基本的圖類,文獻(xiàn)[1]中給出了它們最基本的結(jié)論.圖G的l次方Gl是圖的基本概念,其頂點(diǎn)與圖G相同,兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)是圖G中兩個(gè)頂點(diǎn)的距離不超過(guò)l.本文首先討論了路和圈的l次方多彩色數(shù),并且研究了平方圈和平方路的r-多彩色數(shù).笛卡爾積和強(qiáng)積作為圖運(yùn)算的基本形式,在[8],[10],[12,13]中作者研究了有關(guān)乘積圖的多彩色數(shù)和r-多彩色數(shù).在此基礎(chǔ)上,本文研究平方圈,平方路與路的笛卡爾積,路與路,路與圈強(qiáng)積圖的多彩色數(shù)和r-多彩色數(shù)并得到一些比較好的結(jié)論.本文中主要通過(guò)證明圖的多彩著色數(shù),r-多彩色數(shù)的上下界相等而獲得確切值,其中上界是通過(guò)運(yùn)用相關(guān)代數(shù)運(yùn)算給出具體著色方式而獲得的,下界是通過(guò)反證法及嚴(yán)密推理得到的.
【學(xué)位授予單位】：天津師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 Shun-yi LIU;He-ping ZHANG;Hong-liang LU;Yu-qing LIN;;A Note on the Strong Edge-coloring of Outerplanar Graphs with Maximum Degree 3[J];Acta Mathematicae Applicatae Sinica;2016年04期

2 WAN Min;XU BaoGang;;Acyclic edge coloring of planar graphs without adjacent cycles[J];Science China(Mathematics);2014年02期

3 ;Acyclic edge coloring of graphs with large girths[J];Science China(Mathematics);2012年12期

4 ;Total coloring of embedded graphs of maximum degree at least ten[J];Science China(Mathematics);2010年08期

5 ;Proofs for some known results of equitable coloring[J];商丘師范學(xué)院學(xué)報(bào);2008年09期

6 樂(lè)啟熾 ,崔建忠 ,張學(xué)賓;Imitation design of temperature field in coloring hot dip galvanization process[J];Transactions of Nonferrous Metals Society of China;2002年05期

7 ;Observabilities and reach-abilities of nonlinear DEDS and coloring graphs[J];Chinese Science Bulletin;2001年08期

8 余道衡;賈積有;;APPLYING OONN TO SOLVE MAP-COLORING PROBLEM[J];Journal of Electronics(China);1993年01期

9 ;Acyclic Edge Coloring of Planar Graphs without Adjacent Triangles[J];數(shù)學(xué)研究及應(yīng)用;2012年04期

10 ;k-fold coloring of planar graphs[J];Science China(Mathematics);2010年10期

相關(guān)會(huì)議論文 前4條

1 Meirong Xu;Yige Zhao;;A Matrix Approach to List Coloring problems[A];第36屆中國(guó)控制會(huì)議論文集（A）[C];2017年

2 ;[r,s,t]-Coloring of the Joint Graph C_m∨C_n[A];中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)B卷[C];2011年

3 許曉東;趙文飛;邵澤輝;梁美蓮;;集染色頂點(diǎn)Folkman數(shù)和集染色邊Folkman數(shù)(英文)[A];廣西計(jì)算機(jī)學(xué)會(huì)2014年學(xué)術(shù)年會(huì)論文集[C];2014年

4 ;Decomposition of K_(2n) into n-1 Hamiltonian Cycles and a perfect matching M_i[A];第24屆中國(guó)控制與決策會(huì)議論文集[C];2012年

相關(guān)博士學(xué)位論文 前1條

1 高毓平;圖的邊染色及一些有限制條件的染色[D];山東大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 邵瑞芳;乘積圖的多彩著色[D];天津師范大學(xué);2018年

2 楊芳;幾類圖的點(diǎn)可區(qū)別正常邊染色和全染色[D];西北師范大學(xué);2014年

3 馬莎莎;笛卡爾乘積圖的均勻染色[D];天津師范大學(xué);2016年

4 桂秀平;[D];南京師范大學(xué);2017年

5 張維娟;仙人掌的連續(xù)邊著色[D];新疆大學(xué);2006年

6 林年鋒;平方圖的染色[D];南京師范大學(xué);2004年

7 嚴(yán)曉燕;圖的2-距離染色[D];浙江師范大學(xué);2014年

8 楊超;關(guān)于具有一個(gè)或多個(gè)可區(qū)分約束條件的圖著色研究[D];西北師范大學(xué);2014年

9 黃小佳;關(guān)于圈的D(d)-點(diǎn)可區(qū)別正常全染色的研究[D];西北師范大學(xué);2016年

10 張靜雯;最大度為6的平面圖的全染色[D];浙江師范大學(xué);2011年

，

本文編號(hào)：2636638