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

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

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


本文編號：2581559