k臨界圖(k-critical graph)是一類特殊的圖，指關於連通度的節點臨界圖。若對於圖G上任一節點v，都有k(G-v)<k(G)，則稱G是關於連通度的節點k臨界圖，或者點k板小圖。若對於圖G上任一邊e，都有k-(G-e)<k(G)，稱G為k極小圖，或者邊k極小圖。
基本介紹
- 中文名：k臨界圖
- 外文名：k-critical graph
- 所屬學科：數學
- 所屬問題：組合學(圖與超圖)
- 簡介：關於連通度的節點臨界圖
基本介紹,相關性質,
基本介紹
將k種顏色1，2，…，k塗到G的點上的方法，稱為G的k-點上色法，G的任二相鄰點均有不同顏色的點上色法，稱為合理點上色法。因而，無圈圖G的合理k-點上色法，是V的一個分劃
，此處
為G的無關集(可能為空集)。若G有合理k-點上色法，則稱G為可k-點上色圖。我們將合理點上色法，簡稱為上色法，合理k-點上色法，簡稱為k-上色法．同樣地，可k-點上色圖簡稱為可k-上色圖．顯然，圖為可k-上色圖若且唯若其精簡圖為可k-上色圖．因而研究圖的上色法時，我們只限於討論簡圖。簡圖為可1-上色圖若且唯若其為空圖，簡圖為可2-上色圖若且唯若其為二部圖．使G有k-上色法的最小自然數k，稱為G的點色數或簡稱為G的色數，記為
(G)。如果 (G)=k，稱G為k-色圖。圖1為一個3-色圖。實則，一個3-上色法已表示在圖1上。而且，因圖1不是二部圖，故無2-上色法。
討論所謂臨界圖的性質，對研究上色法是有用處的。圖G稱為臨界圖，如果對每一H⊂G，有 (H)< (G)。狄拉克於1952年首先研究這種圖。若圖G既為k-色圖又為臨界圖，則稱為k-臨界圖。每一k-色圖有k-臨界子圖。圖2為格呂卻(Grötzsch)的4-臨界圖。由臨界圖的定義，易知臨界圖是連通圖。
圖1
圖2相關性質
定理1 若G為k-臨界圖，則
證明 用反證法。若G為k-臨界圖，且
，讓v是階數為δ的點，即dG(v)=δ。因G為k-臨界圖，則G-v為可(k-1)-上色圖。設
是G-v的(k-1)-上色法。因dG(v)=δ<k-1，故v必同某Vi的每一點都不相鄰。這樣一來，
為G的(k-1)-上色法，這同G為k-色圖矛盾。
系1 k-色圖至少有k個點，它們都有階數≥k-1。
證明 讓G為k-色圖，H為G的k-臨界子圖，據定理1，若v∈V(H)，則dH(v)≥k-1。因而，dG(v)≥k-1，又因H為k-色圖，故v(H)≥k。
系2 設G為(無圈)圖，則(G)≤Δ+1。
證明 由系1，即得結論。
讓S是連通圖G的點割集，且讓G-S的一切分支的點集為
，則子圖Gi=G[Vi∪S]稱為G的S-分支(或S-連通支)(見圖3)，在
上各給出一個上色法。若對每一v∈S，這n個上色法在n上均塗相同的顏色，則稱這n個上色法在S上一致。
圖3（a） (a)G
圖3（b） G的{u，v}-分支定理2 讓G為臨界圖，若S⊂V(G)為G的點割集，則S不是G的完整集。
系3 臨界圖為塊。
證明 若v為割裂點，則{v}為點割集，且亦為完整集。因而同定理2矛盾，所以，臨界圖為塊。
定理2的另一推論是，若k-臨界圖G有2-點割集{u，v}，則u，v不相鄰．設G為k-臨界圖．我們稱G的{u，v}-分支Gi是第一型分支，如果Gi的每一(k-1)-上色法在u，v上塗相同顏色，稱G的{u，v}-分支Gi是第二型分支，若Gi的每一(k-1)-上色法在u，v上塗不同顏色(見圖4)。
圖4（a）
圖4（b）定理3 (狄拉克，1953)讓G是k-臨界圖，且有2-點剖集{u，v}，則
(i)G=G1∪G2，此處Gi是第i型(i=1，2){u，v}-分支；
(ii) G1+uv和G1。uv都是k-臨界圖。
系4 讓G是k-臨界圖，且{u，v}為其2-點割集，則
