狄拉克定理解释了图染色数与完全细分图的关系。
定理描述
任何一个最小染色数大于等于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_+},我们称最小的那个k为\chi(G)。
细分边
给定一条边e=v_1v_2，在边e中添加一个点w使得e变为一条由v_1w,wv_2组成的路径，称为边的细分。
细分图
对于图G，将其中一些边进行细分而得到的图G'称为G的细分图
色临界图
如果对于图G，其任意真子图G'\subset 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)\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'为H_i\cup \{x,y\}的生成子图，有\chi(H'+xy)=\chi(G)=4。由于n(H'+xy)，所以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)\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_1y,e_2=v_2y,e_3=v_3y得到新的图H^\ast，则仍然有\kappa(H^\ast)\ge 3。所以对x,y\in H^\ast,存在三条从x到y内部互不相交的路径P'_1=P_1+v_1y,P'_2=P_2+v_2y,P'_3=P_3+v_3y。又由于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，目前是个开放问题
参考来源
评论 (0)