狄拉克定理

狄拉克定理解释了图染色数与完全细分图的关系。

定理描述

任何一个最小染色数大于等于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$，目前是个开放问题