查看“︁狄拉克定理”︁的源代码

'''狄拉克定理'''解释了图染[[图着色问题|色数]]与完全[[细分 (图论)|细分图]]的关系。

== 定理描述 ==
任何一个最小染色数大于等于4的图（<math>\chi(G)\ge 4</math>）均存在一个4阶完全图的细分图（<math>K_4-subdivision</math>）。

== 相关背景介绍 ==

=== 图染色数 ===
对于给定的图<math>G</math>，存在<math>k</math>种颜色和一种染色方案，将图中<math>G</math>每一个顶点都染成<math>k</math>种颜色中的一种。如果染色方案满足一下条件，那么将称该染色方案为恰当的染色方案：对于图<math>G</math>中任意两个顶点<math>u,v</math>，如果<math>uv\in E(G)</math>，那么<math>u,v</math>所染成的颜色不同。

对于图<math>G</math>，如果存在一个<math>k</math>种颜色的恰当染色方案，我们称<math>G</math>是染色的。在所有满足条件的<math>k\in \mathbb{Z_+}</math>,我们称最小的那个<math>k</math>为<math>\chi(G)</math>。

=== 细分边 ===
给定一条边<math>e=v_1v_2</math>，在边<math>e</math>中添加一个点<math>w</math>使得<math>e</math>变为一条由<math>v_1w,wv_2</math>组成的路径，称为边的细分。

=== 细分图 ===
对于图<math>G</math>，将其中一些边进行细分而得到的图<math>G'</math>称为<math>G</math>的细分图

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

== 定理证明 ==
对图中点的数量<math>n(G)</math>进行递归

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

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

由于<math>H</math>是色临界图，<math>H</math>不存在割点。

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

如果<math>\kappa(H)\ge 3</math>，任意选择<math>x\in V(H)</math>，有<math>\kappa(H-x)\ge 2</math>。所以存在一个环<math>C\in H-x</math>。选取环<math>C</math>上任意三个点<math>v_1,v_2,v_3
</math>，在<math>H</math>中添加一个点<math>u</math>与三条边<math>e_1=v_1y,e_2=v_2y,e_3=v_3y</math>得到新的图<math>H^\ast</math>，则仍然有<math>\kappa(H^\ast)\ge 3</math>。所以对<math>x,y\in H^\ast</math>,存在三条从<math>x</math>到<math>y</math>内部互不相交的路径<math>P'_1=P_1+v_1y,P'_2=P_2+v_2y,P'_3=P_3+v_3y</math>。又由于<math>v_1,v_2,v_3\in C
</math>。存在环上3条内部互不相交的路径<math>P_4,P_5,P_6
</math>分别从<math>v_1
</math>到<math>v_2

</math>，<math>v_2

</math>到<math>v_3
</math>，<math>v_3
</math>到<math>v_1
</math>。则<math>P_1\cup P_2\cup P_3\cup P_4\cup P_5\cup P_6
</math>是图<math>G</math>的一个子图且为4阶完全图的细分图。
<ref>{{cite book|author1=Douglas B.West|title=Introduction to Graph Theory|date=2002|publisher=Pearson Enducation|isbn=81-7808-830-4|pages=232-240}}</ref>

== Hajos 猜想 ==
任何一个最小染色数大于等于<math>k</math>的图（<math>\chi(G)\ge k</math>）均存在一个<math>k</math>阶完全图的细分图（<math>K_{k}-subdivision</math>）。

当<math>k=2,3,4</math>的时候，答案是肯定的。

当<math>k\ge 7</math>的时候，答案是否定的。

对于<math>k=5,6</math>，目前是个开放问题

== 参考来源 ==
<references />

[[Category:数学定理]]
[[Category:圖染色]]