1、無(wú)環(huán)圖G的一個(gè)邊著色π是從邊集E到顏色集C的一個(gè)映射π：E→C，使得G中任何兩條相鄰的邊均有不同的像。若|C|=k，則稱π是G的一個(gè)k-邊著色。使得G有k-邊著色的最小k值稱為G的邊色數(shù)，即：x'(G)=min{k|G存在一個(gè)k-邊著色}。著名的Vizing定理表明：若G是簡(jiǎn)單圖，則x'(G)≤△+1。根據(jù)邊著色的定義可知x'(G)≥△。于是人們根據(jù)圖的邊色數(shù)將簡(jiǎn)單圖分為兩類，即若x'(G)=△，則稱G是第一類圖；若x'(G)=△+1，

2、則稱G是第二類圖。設(shè)G是連通第二類圖，且對(duì)G的任何邊e都有：x'(G-e)＜x'(G)，則稱G是臨界圖。本文根據(jù)臨界圖的定義和VAL定理討論了△≥5的臨界圖的若干性質(zhì)，為沖擊臨界圖猜想作了準(zhǔn)備工作。 圖G的一個(gè)頂點(diǎn)著色φ是從頂點(diǎn)集V到顏色集C的一個(gè)映射φ：V→C，使得G中任何兩個(gè)相鄰的頂點(diǎn)均無(wú)相同的像。若|C|=k，則稱φ是G的一個(gè)k-頂點(diǎn)著色。使得G有k-頂點(diǎn)著色的最小k值稱為G的頂點(diǎn)色數(shù)，用x(G)表示。 設(shè)I(G)={(v，e)|

3、v∈V，e∈E且v與e相關(guān)聯(lián)}是G的關(guān)聯(lián)集。稱G的兩個(gè)關(guān)聯(lián)(v，e)和(w，f)相鄰當(dāng)且僅當(dāng)下列三種情況之一成立：(1)v=w；(2)e=f；(3)vw=e或vw=f。圖G的一個(gè)關(guān)聯(lián)著色σ是從關(guān)聯(lián)集I(G)到顏色集c的一個(gè)映射σ：I(G)→C，使得I(G)中任何兩個(gè)相鄰的關(guān)聯(lián)都有不同的像。若σ：I(G)→C是G的一個(gè)關(guān)聯(lián)著色且|C|=k，則稱G是k-可關(guān)聯(lián)著色的。使得G有k-可關(guān)聯(lián)著色的最小k值稱為G的關(guān)聯(lián)色數(shù)，用x_i(G)表示。 本

4、文根據(jù)關(guān)聯(lián)著色和頂點(diǎn)著色的定義、性質(zhì)給出了關(guān)聯(lián)圖的兩個(gè)等價(jià)定義，并在此基礎(chǔ)上討論了關(guān)聯(lián)圖的一些性質(zhì)以及關(guān)聯(lián)著色與頂點(diǎn)著色的若干關(guān)系；利用窮染法和換色技巧確定了Meredith's圖的關(guān)聯(lián)色數(shù)；從圖的結(jié)構(gòu)性質(zhì)出發(fā)，利用雙重歸納法和換色技巧證明了△≥4的系列平行圖都存在一個(gè)(△+2，2)-關(guān)聯(lián)著色；根據(jù)(k，l)-關(guān)聯(lián)著色的定義和△=4，mad(G)＜3的圖的結(jié)構(gòu)性質(zhì)，利用歸納法和換色技巧證明了△=4，mad(G)＜3的圖G存在一個(gè)(6，2