仙人掌的連續(xù)邊著色.pdf

1、設(shè)G是簡(jiǎn)單圖，用顏色1; 2, 3,…對(duì)G的邊正常著色，如果在每一頂點(diǎn)表現(xiàn)的顏色構(gòu)成一個(gè)連續(xù)的整數(shù)集合，那么就稱這個(gè)著色是連續(xù)的.圖的連續(xù)邊著色對(duì)應(yīng)于沒(méi)有等待時(shí)間的日程安排問(wèn)題.不是所有的圖都有連續(xù)邊著色.圖G的虧度de f (G)是粘在G上使得它可連續(xù)著色的懸掛邊的最小數(shù)目側(cè). 通常要確定一個(gè)圖是否有連續(xù)邊著色是比較困難的，而且己刻劃的圖只有很少的一部分.事實(shí)上，Sevastjanov在[s]中己經(jīng)證明了即使是對(duì)一個(gè)給定的二部圖，

2、要確定它是否有連續(xù)邊著色也是NP完全的. 仙人掌是一個(gè)每個(gè)塊是圈或Kz的圖.從定義可知一個(gè)仙人掌的任意兩個(gè)不同的圈至多有一個(gè)公共點(diǎn).用of必表示圖‘中包含的奇圈個(gè)數(shù)，尺表示由n個(gè)只有一個(gè)公共頂點(diǎn)的三角形構(gòu)成的圖.如果一個(gè)圖G有導(dǎo)出子圖G1和Gz使得G二Gl、 Gz并且G1nGz=Ifi，則稱G是G,和G:在頂點(diǎn)?的粘，記作G二Gi vv Gz，其中?E Y(Gl n Gz). 在本文中，我們研究仙人掌的連續(xù)邊著色問(wèn)題.我們確定了