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

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

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