基本介紹
- 中文名：色臨界圖
- 外文名：color-critical graph
- 適用範圍：數理科學
定義,性質,分類,
定義
如果對圖 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 條邊。此猜想至今尚未解決。
