若干圖的連續(xù)邊著色.pdf

1、具有重要的實(shí)際意義和理論意義的圖的連續(xù)邊著色問(wèn)題是圖論中的熱點(diǎn)話題之一，它在組合分析和日程安排理論上有著非常廣泛的應(yīng)用.連續(xù)邊著色問(wèn)題首先是由Asratian和Kamalian在1987年提出的，其內(nèi)容為:對(duì)于簡(jiǎn)單圖G用顏色1,2.3…對(duì)其邊正常著色，如果每一個(gè)頂點(diǎn)表現(xiàn)的顏色構(gòu)成一個(gè)連續(xù)的整數(shù)集合，那么就稱(chēng)這個(gè)邊著色是連續(xù)的.許多圖是不可連續(xù)邊著色的，為了測(cè)量與連續(xù)邊著色的漸進(jìn)程度，我們引入了圖的一個(gè)新的不變量:圖的虧度.圖G的虧度de

2、f(G)是指加在G上使它可連續(xù)邊著色的懸掛邊的最小數(shù)目.本文分為三章，主要研究了若干圖的連續(xù)邊著色性.
　　第一章我們給出了本文將用到的圖論的主要術(shù)語(yǔ)、記號(hào)和基本概念.在第二節(jié)我們介紹了連續(xù)邊著色方面的基本結(jié)論.
　　第二章主要研究了一些圈圖的連續(xù)邊著色.在這章中，根據(jù)3-圈圖的結(jié)構(gòu)和性質(zhì)，以及連續(xù)邊著色的定義，得到了幾類(lèi)3-圈圖的虧度，解決了它們的連續(xù)邊著色問(wèn)題.進(jìn)而推廣到k-圈圖，我們通過(guò)運(yùn)用歸納法和反證法的思想，討論了

3、一種k-圈圖的連續(xù)邊著色及其虧度問(wèn)題.
　　主要結(jié)論敘述如下:
　　(1)若G是四條內(nèi)部不相交的(u，v)路的并圖，則def(G)={0，|E(G)|為偶;1,|E(G)|為奇.
　　(2)令C1,C2，C3是三個(gè)不相交的圈，Pi(i=1，2)是兩條不相交的(V(Ci)，V(Ci+1))路.若G是C1，C2，C3，P1和P2的并圖，則def(G)=0.
　　(3)若G是僅有一個(gè)公共頂點(diǎn)的n（n≥1）個(gè)圈C1，C2