【摘要】：一個圖G的k-全染色是指用k種顏色對G的頂點(diǎn)和邊進(jìn)行染色,使得相鄰或相關(guān)聯(lián)的元素染不同的顏色.圖G的全色數(shù)χ_T(G)是使G存在k-全染色的最小整數(shù)k.證明了最大度為7且3-圈與5-圈不正常相交的平面圖的全色數(shù)是8.
【圖文】：

，使得Ｍ飽和所有的２－點(diǎn)．由引理３，定義：如果ｕｖ∈Ｍ且ｄ（ｕ）＝２，那么稱ｖ是ｕ的２－主點(diǎn)．由引理２和引理３，Ｇ中每一個２－點(diǎn)都有一個２－主點(diǎn)，且只有７－點(diǎn)才能成為２－主點(diǎn)，一個７－點(diǎn)至多只能成為一個２－點(diǎn)的２－主點(diǎn)．引理４［１３］設(shè)ｖ是Ｇ的一個７－點(diǎn)且ｎ２（ｖ）≥１，則ｎ４＋（ｖ）≥１．引理５［１１］Ｇ沒有（４，４，７－）－面．圖１Ｇ的可約構(gòu)形Ｆｉｇ．１ＲｅｄｕｃｉｂｌｅＣｏｎｆｉｇｕｒａｔｉｏｎｓｏｆＧ引理６［１１］Ｇ不包含圖１的５個子圖．用·表示的點(diǎn)在原圖中沒有圖示以外的其他鄰點(diǎn)．我們將通過歐拉公式和權(quán)轉(zhuǎn)移方法導(dǎo)出定理１所需的矛盾．由握手定理∑ｖ∈Ｖｄ（ｖ）＝２Ｅ＝∑ｆ∈Ｆｄ（ｆ）可將連通平面圖的歐拉公式Ｖ－Ｅ＋Ｆ＝２改寫成∑ｖ∈Ｖ（２ｄ（ｖ）－６）＋∑ｆ∈Ｆ（ｄ（ｆ）－６）＝－１２＜０．首先給Ｇ的頂點(diǎn)ｖ分配初始權(quán)ｃｈ（ｖ）＝２ｄ（ｖ）－６，給Ｇ的面ｆ分配初始權(quán)ｃｈ（ｆ）＝ｄ（ｆ）－６，則∑ｘ∈Ｖ∪Ｆｃｈ（ｘ）＝－１２．以下將定義一個權(quán)轉(zhuǎn)移規(guī)則，重新分配點(diǎn)和面的權(quán)，記ｃｈ′（ｘ）是重新分配點(diǎn)和面的權(quán)后元素ｘ∈Ｖ∪Ｆ的新權(quán)，將要證明對每個ｘ∈Ｖ∪Ｆ都有ｃｈ′（ｘ）≥０．而由于權(quán)轉(zhuǎn)移過程保持權(quán)的總量不變，故０≤∑ｘ∈Ｖ∪Ｆｃｈ′（ｘ）＝∑ｘ∈Ｖ∪Ｆｃｈ

，使得Ｍ飽和所有的２－點(diǎn)．由引理３，定義：如果ｕｖ∈Ｍ且ｄ（ｕ）＝２，那么稱ｖ是ｕ的２－主點(diǎn)．由引理２和引理３，Ｇ中每一個２－點(diǎn)都有一個２－主點(diǎn)，且只有７－點(diǎn)才能成為２－主點(diǎn)，一個７－點(diǎn)至多只能成為一個２－點(diǎn)的２－主點(diǎn)．引理４［１３］設(shè)ｖ是Ｇ的一個７－點(diǎn)且ｎ２（ｖ）≥１，則ｎ４＋（ｖ）≥１．引理５［１１］Ｇ沒有（４，４，７－）－面．圖１Ｇ的可約構(gòu)形Ｆｉｇ．１ＲｅｄｕｃｉｂｌｅＣｏｎｆｉｇｕｒａｔｉｏｎｓｏｆＧ引理６［１１］Ｇ不包含圖１的５個子圖．用·表示的點(diǎn)在原圖中沒有圖示以外的其他鄰點(diǎn)．我們將通過歐拉公式和權(quán)轉(zhuǎn)移方法導(dǎo)出定理１所需的矛盾．由握手定理∑ｖ∈Ｖｄ（ｖ）＝２Ｅ＝∑ｆ∈Ｆｄ（ｆ）可將連通平面圖的歐拉公式Ｖ－Ｅ＋Ｆ＝２改寫成∑ｖ∈Ｖ（２ｄ（ｖ）－６）＋∑ｆ∈Ｆ（ｄ（ｆ）－６）＝－１２＜０．首先給Ｇ的頂點(diǎn)ｖ分配初始權(quán)ｃｈ（ｖ）＝２ｄ（ｖ）－６，給Ｇ的面ｆ分配初始權(quán)ｃｈ（ｆ）＝ｄ（ｆ）－６，則∑ｘ∈Ｖ∪Ｆｃｈ（ｘ）＝－１２．以下將定義一個權(quán)轉(zhuǎn)移規(guī)則，重新分配點(diǎn)和面的權(quán)，記ｃｈ′（ｘ）是重新分配點(diǎn)和面的權(quán)后元素ｘ∈Ｖ∪Ｆ的新權(quán)，將要證明對每個ｘ∈Ｖ∪Ｆ都有ｃｈ′（ｘ）≥０．而由于權(quán)轉(zhuǎn)移過程保持權(quán)的總量不變，，故０≤∑ｘ∈Ｖ∪Ｆｃｈ′（ｘ）＝∑ｘ∈Ｖ∪Ｆｃｈ


本文編號：2581559