狄拉克定理

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

定理描述

任何一个最小染色数大于等于4的图（$\chi (G)\ge 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}}_{\mathbb{+}}$,我们称最小的那个$k$为$\chi (G)$。

细分边

给定一条边$e=v_1{v}_2$，在边$e$中添加一个点$w$使得$e$变为一条由$v_{1}w,w{v}_2$组成的路径，称为边的细分。

细分图

对于图$G$，将其中一些边进行细分而得到的图$G^{\prime }$称为$G$的细分图

色临界图

如果对于图$G$，其任意真子图$G^{\prime }\subset G$均满足$\chi (G^{\prime })<\chi (G)$，则称$G$为色临界图。对于任何一张图$G$，均存在$G^{\prime }\subseteq G,\chi (G^{\prime })=\chi (G)$且$G^{\prime }$是色临界图。

定理证明

对图中点的数量$n(G)$进行递归

当$n(G)=4$的时候，$G$的最小染色数为4，故$G$只能为一张完全图，所以$G$中存在$K_4$的细分图（自身）。

假设当$n(G)\le k-1$时成立，现考虑当$n(G)=k$时。由于$\chi (G)\ge 4$，存在$H\subseteq G,\chi (H)=4$且$H$是色临界图。由子图可知，$n(H)\le k$。

由于$H$是色临界图，$H$不存在割点。

如果$\kappa (H)=2$，设$S=\{x,y\}$为$H$的割集。根据色临界图割集的性质，$xy\notin E(H)$且任意选择$H_i$为$H-\{x,y\}$的连通分支，$H^{\prime }$为$H_i\cup \{x,y\}$的生成子图，有$\chi (H^{\prime }+xy)=\chi (G)=4$。由于$n(H^{\prime }+xy)<n(G)$，所以$H^{\prime }+xy$中存在一个4阶完全图的细分图$A$。如果$xy\notin A$，则$A\subseteq H^{\prime }\subseteq G$。那么根据归纳假设，$G$中存在4阶完全图的细分图$A$。如果$xy\in A$，对于$H-\{x,y\}$的另一个连通分支$H_j$，$H_j\cup \{x,y\}$是连通图，存在一条从$x$到$y$的路径$P\in H^{\prime }$。则$P\notin A$，所以$A-xy\cup P$是一个4阶完全图的细分图。

如果$\kappa (H)\ge 3$，任意选择$x\in V(H)$，有$\kappa (H-x)\ge 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 })\ge 3$。所以对$x,y\in H^{\ast }$,存在三条从$x$到$y$内部互不相交的路径$P{\text{'}}_1=P_1+v_{1}y,P{\text{'}}_2=P_2+v_{2}y,P{\text{'}}_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)\ge k$）均存在一个$k$阶完全图的细分图（$K_k-subdivision$）。

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

当$k\ge 7$的时候，答案是否定的。

对于$k=5,6$，目前是个开放问题