狄拉克定理解釋了圖染色數與完全細分圖的關係。
定理描述[編輯]
任何一個最小染色數大於等於4的圖(
)均存在一個4階完全圖的細分圖(
)。
相關背景介紹[編輯]
圖染色數[編輯]
對於給定的圖
,存在
種顏色和一種染色方案,將圖中
每一個頂點都染成
種顏色中的一種。如果染色方案滿足一下條件,那麼將稱該染色方案為恰當的染色方案:對於圖
中任意兩個頂點
,如果
,那麼
所染成的顏色不同。
對於圖
,如果存在一個
種顏色的恰當染色方案,我們稱
是染色的。在所有滿足條件的
,我們稱最小的那個
為
。
細分邊[編輯]
給定一條邊
,在邊
中添加一個點
使得
變為一條由
組成的路徑,稱為邊的細分。
細分圖[編輯]
對於圖
,將其中一些邊進行細分而得到的圖
稱為
的細分圖
色臨界圖[編輯]
如果對於圖
,其任意真子圖
均滿足
,則稱
為色臨界圖。對於任何一張圖
,均存在
且
是色臨界圖。
定理證明[編輯]
對圖中點的數量
進行遞歸
當
的時候,
的最小染色數為4,故
只能為一張完全圖,所以
中存在
的細分圖(自身)。
假設當
時成立,現考慮當
時。由於
,存在
且
是色臨界圖。由子圖可知,
。
由於
是色臨界圖,
不存在割點。
如果
,設
為
的割集。根據色臨界圖割集的性質,
且任意選擇
為
的連通分支,
為
的生成子圖,有
。由於
,所以
中存在一個4階完全圖的細分圖
。如果
,則
。那麼根據歸納假設,
中存在4階完全圖的細分圖
。如果
,對於
的另一個連通分支
,
是連通圖,存在一條從
到
的路徑
。則
,所以
是一個4階完全圖的細分圖。
如果
,任意選擇
,有
。所以存在一個環
。選取環
上任意三個點
,在
中添加一個點
與三條邊
得到新的圖
,則仍然有
。所以對
,存在三條從
到
內部互不相交的路徑
。又由於
。存在環上3條內部互不相交的路徑
分別從
到
,
到
,
到
。則
是圖
的一個子圖且為4階完全圖的細分圖。
[1]
Hajos 猜想[編輯]
任何一個最小染色數大於等於
的圖(
)均存在一個
階完全圖的細分圖(
)。
當
的時候,答案是肯定的。
當
的時候,答案是否定的。
對於
,目前是個開放問題
參考來源[編輯]
- ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002: 232–240. ISBN 81-7808-830-4.