臨界圖的若干性質和圖的關聯(lián)著色的研究.pdf

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

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

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

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