若干圖類的星邊染色.pdf

1、圖的染色問題是圖論研究中的重要問題之一，有重要的理論價值和應(yīng)用背景。2004年，F(xiàn)ertin等提出了星染色的概念。2006年，劉信生等提出了星邊染色的概念，若圖G的一個正常邊染色滿足G中沒有長為4的路是2-邊染色的，則稱此染色是G的一個星邊染色，使得G有星邊染色的最小顏色數(shù)稱為星邊色數(shù)，記作X's(G)。圖的星邊染色不僅對研究星染色有重要的意義，而且星邊染色和星邊色數(shù)與無圈邊染色和無圈邊色數(shù)a'(G)(Grünbaum，1973)以及強(qiáng)

2、邊染色和強(qiáng)邊色數(shù)Sx'(G)(Erdos，1986)有密切關(guān)系。到目前為止，關(guān)于星邊染色還有很多問題有待解決。
　　 本文研究了一些特殊圖類的星邊染色，主要有以下結(jié)果：
　　 1．研究了若干笛卡爾積圖的星邊染色，并分別得到了Pm□Pn、Pm□Cn、Pm□Sn、Pm□Fn、Pm□Wn的星邊色數(shù)；
　　 2．研究了廣義Petersen圖的星邊染色，進(jìn)而得到了P(n，2)的星邊色數(shù)；
　　 3．研究了路與路聯(lián)圖