跳至內容

狄拉克定理

維基百科,自由的百科全書

狄拉克定理解釋了圖染色數與完全細分圖的關係。

定理描述

任何一個最小染色數大於等於4的圖()均存在一個4階完全圖的細分圖()。

相關背景介紹

圖染色數

對於給定的圖,存在種顏色和一種染色方案,將圖中每一個頂點都染成種顏色中的一種。如果染色方案滿足一下條件,那麼將稱該染色方案為恰當的染色方案:對於圖中任意兩個頂點,如果,那麼所染成的顏色不同。

對於圖,如果存在一個種顏色的恰當染色方案,我們稱是染色的。在所有滿足條件的,我們稱最小的那個

細分邊

給定一條邊,在邊中添加一個點使得變為一條由組成的路徑,稱為邊的細分。

細分圖

對於圖,將其中一些邊進行細分而得到的圖稱為的細分圖

色臨界圖

如果對於圖,其任意真子圖均滿足,則稱為色臨界圖。對於任何一張圖,均存在是色臨界圖。

定理證明

對圖中點的數量進行遞歸

的時候,的最小染色數為4,故只能為一張完全圖,所以中存在的細分圖(自身)。

假設當時成立,現考慮當時。由於,存在是色臨界圖。由子圖可知,

由於是色臨界圖,不存在割點。

如果,設的割集。根據色臨界圖割集的性質,且任意選擇的連通分支,的生成子圖,有。由於,所以中存在一個4階完全圖的細分圖。如果,則。那麼根據歸納假設,中存在4階完全圖的細分圖。如果,對於的另一個連通分支是連通圖,存在一條從的路徑。則,所以是一個4階完全圖的細分圖。

如果,任意選擇,有。所以存在一個環。選取環上任意三個點,在中添加一個點與三條邊得到新的圖,則仍然有。所以對,存在三條從內部互不相交的路徑。又由於。存在環上3條內部互不相交的路徑分別從。則是圖的一個子圖且為4階完全圖的細分圖。 [1]

Hajos 猜想

任何一個最小染色數大於等於的圖()均存在一個階完全圖的細分圖()。

的時候,答案是肯定的。

的時候,答案是否定的。

對於,目前是個開放問題

參考來源

  1. ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002: 232–240. ISBN 81-7808-830-4.