色臨界圖

色臨界圖

色臨界圖亦稱點著色臨界圖,是一類與色數有關的極圖。如果對圖 G 的每個真子圖 H,H 的色數小於 G 的色數,則 G 稱為色臨界圖。

定義

如果對圖 G 的每個真子圖 H,H 的色數小於 G 的色數,則 G 稱為色臨界圖(color-critical graph)。如果 G 是色臨界圖且色數為 k,則稱 G 為k臨界圖(k-critical graph)。從定義不難推知,每個色臨界圖都是連通的。

性質

色臨界圖是狄拉克(G.A.Dirac) 於1952 年首先研究的。

狄拉克在1953年證明:任意 k 臨界圖都是 (k-1) 邊連通的。k 臨界圖 G 還有如下性質:

(1) G 的最小度 δ(G) > k-1;

(2) G 的任意頂點割不是團。

分類

臨界圖[critical graph]:在圖論中,最重要的兩類臨界圖是色臨界圖和邊色臨界圖。

在邊染色中,根據韋津定理,可以把所有的簡單圖分成兩類:若 G 的邊色數等於它的最大度,則 G 屬於第一類圖,否則 G 屬於第二類圖。

然而要確定圖究竟屬於哪一類是極其困難的,為此,韋津引入邊色臨界圖的概念。

設 G 是連通的第二類圖,且對 G 的任意邊 e,均有 G\ e 的邊色數小於 G 的邊色數,則稱 G 為邊色臨界圖(edge-color-critical graph )。

若 G是最大度為 △的邊色臨界圖,則稱 G 為 △臨界圖( A-criticalgraph)。

關於邊色臨界圖邊數的下界,有如下韋津猜想:任意一個 n 階 △臨界圖至少有 (n△- n+3)/2 條邊。此猜想至今尚未解決。  

相關詞條

熱門詞條

聯絡我們