第Ⅱ類正則圖的色特征.pdf

1、由Vizing定理可知所有的k_正則簡單圖可分為兩類:邊色數(shù)為k的第工類圖和邊色數(shù)為k+1的第II類圖。很多著名的問題限制在第工類圖上時比較容易解決，然而在第II類圖上考慮時卻異常困難。其中最引人關注的是第II類3一正則圖，一些著名猜想的證明，如'lhtte的S一流猜想、圈雙覆蓋猜想((CDCC)等(見1)） (2J)，都是在涉及到第Ii類3一正則圖時遇到了困難。另外，四色定理等價于“每一個無割邊的3一正則平面圖是第I類圖”(見同，)

2、。因此，我們致力于研究第II類正則圖的性質和結構。 為此，我們研究第II類正則圖的一個參數(shù)一色特征。令G是一個第II類k-正則圖，。是G的一個正常k+1一邊著色，盡_ {e E L}' } c(e) _i}, i=0,1,…,k。定義。(c)=min{ } E; }}2=O,l,...,k}，我們稱。(G)=min }o(c)}是G的色特征，其中c(c)是由G的所有正常k+1一邊著色組成cEC(G)’的集合。對于有重邊的邊色數(shù)為k+