狄拉克定理

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

定理描述

任何一個最小染色數大於等於4的圖（$\chi (G)\geq 4$）均存在一個4階完全圖的細分圖（$K_{4}-subdivision$）。

相關背景介紹

圖染色數

對於給定的圖$G$，存在$k$種顏色和一種染色方案，將圖中$G$每一個頂點都染成$k$種顏色中的一種。如果染色方案滿足一下條件，那麼將稱該染色方案為恰當的染色方案：對於圖$G$中任意兩個頂點$u,v$，如果$uv\in E(G)$，那麼$u,v$所染成的顏色不同。

對於圖$G$，如果存在一個$k$種顏色的恰當染色方案，我們稱$G$是染色的。在所有滿足條件的$k\in \mathbb {Z_{+}}$,我們稱最小的那個$k$為$\chi (G)$。

細分邊

給定一條邊$e=v_{1}v_{2}$，在邊$e$中添加一個點$w$使得$e$變為一條由$v_{1}w,wv_{2}$組成的路徑，稱為邊的細分。

細分圖

對於圖$G$，將其中一些邊進行細分而得到的圖$G'$稱為$G$的細分圖

色臨界圖

如果對於圖$G$，其任意真子圖$G'\subset G$均滿足$\chi (G')<\chi (G)$，則稱$G$為色臨界圖。對於任何一張圖$G$，均存在$G'\subseteq G,\chi (G')=\chi (G)$且$G'$是色臨界圖。

定理證明

對圖中點的數量$n(G)$進行遞歸

當$n(G)=4$的時候，$G$的最小染色數為4，故$G$只能為一張完全圖，所以$G$中存在$K_{4}$的細分圖（自身）。

假設當$n(G)\leq k-1$時成立，現考慮當$n(G)=k$時。由於$\chi (G)\geq 4$，存在$H\subseteq G,\chi (H)=4$且$H$是色臨界圖。由子圖可知，$n(H)\leq k$。

由於$H$是色臨界圖，$H$不存在割點。

如果$\kappa (H)=2$，設$S=\{x,y\}$為$H$的割集。根據色臨界圖割集的性質，$xy\notin E(H)$且任意選擇$H_{i}$為$H-\{x,y\}$的連通分支，$H'$為$H_{i}\cup \{x,y\}$的生成子圖，有$\chi (H'+xy)=\chi (G)=4$。由於$n(H'+xy)<n(G)$，所以$H'+xy$中存在一個4階完全圖的細分圖$A$。如果$xy\notin A$，則$A\subseteq H'\subseteq G$。那麼根據歸納假設，$G$中存在4階完全圖的細分圖$A$。如果$xy\in A$，對於$H-\{x,y\}$的另一個連通分支$H_{j}$，$H_{j}\cup \{x,y\}$是連通圖，存在一條從$x$到$y$的路徑$P\in H'$。則$P\notin A$，所以$A-xy\cup P$是一個4階完全圖的細分圖。

如果$\kappa (H)\geq 3$，任意選擇$x\in V(H)$，有$\kappa (H-x)\geq 2$。所以存在一個環$C\in H-x$。選取環$C$上任意三個點$v_{1},v_{2},v_{3}$，在$H$中添加一個點$u$與三條邊$e_{1}=v_{1}y,e_{2}=v_{2}y,e_{3}=v_{3}y$得到新的圖$H^{\ast }$，則仍然有$\kappa (H^{\ast })\geq 3$。所以對$x,y\in H^{\ast }$,存在三條從$x$到$y$內部互不相交的路徑$P'_{1}=P_{1}+v_{1}y,P'_{2}=P_{2}+v_{2}y,P'_{3}=P_{3}+v_{3}y$。又由於$v_{1},v_{2},v_{3}\in C$。存在環上3條內部互不相交的路徑$P_{4},P_{5},P_{6}$分別從$v_{1}$到$v_{2}$，$v_{2}$到$v_{3}$，$v_{3}$到$v_{1}$。則$P_{1}\cup P_{2}\cup P_{3}\cup P_{4}\cup P_{5}\cup P_{6}$是圖$G$的一個子圖且為4階完全圖的細分圖。

Hajos 猜想

任何一個最小染色數大於等於$k$的圖（$\chi (G)\geq k$）均存在一個$k$階完全圖的細分圖（$K_{k}-subdivision$）。

當$k=2,3,4$的時候，答案是肯定的。

當$k\geq 7$的時候，答案是否定的。

對於$k=5,6$，目前是個開放問題