跳转到内容

狄拉克定理

维基百科,自由的百科全书

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

定理描述

任何一个最小染色数大于等于4的图()均存在一个4阶完全图的细分图()。

相关背景介绍

图染色数

对于给定的图,存在种颜色和一种染色方案,将图中每一个顶点都染成种颜色中的一种。如果染色方案满足一下条件,那么将称该染色方案为恰当的染色方案:对于图中任意两个顶点,如果,那么所染成的颜色不同。

对于图,如果存在一个种颜色的恰当染色方案,我们称是染色的。在所有满足条件的,我们称最小的那个

细分边

给定一条边,在边中添加一个点使得变为一条由组成的路径,称为边的细分。

细分图

对于图,将其中一些边进行细分而得到的图称为的细分图

色临界图

如果对于图,其任意真子图均满足,则称为色临界图。对于任何一张图,均存在是色临界图。

定理证明

对图中点的数量进行递归

的时候,的最小染色数为4,故只能为一张完全图,所以中存在的细分图(自身)。

假设当时成立,现考虑当时。由于,存在是色临界图。由子图可知,

由于是色临界图,不存在割点。

如果,设的割集。根据色临界图割集的性质,且任意选择的连通分支,的生成子图,有。由于,所以中存在一个4阶完全图的细分图。如果,则。那么根据归纳假设,中存在4阶完全图的细分图。如果,对于的另一个连通分支是连通图,存在一条从的路径。则,所以是一个4阶完全图的细分图。

如果,任意选择,有。所以存在一个环。选取环上任意三个点,在中添加一个点与三条边得到新的图,则仍然有。所以对,存在三条从内部互不相交的路径。又由于。存在环上3条内部互不相交的路径分别从。则是图的一个子图且为4阶完全图的细分图。 [1]

Hajos 猜想

任何一个最小染色数大于等于的图()均存在一个阶完全图的细分图()。

的时候,答案是肯定的。

的时候,答案是否定的。

对于,目前是个开放问题

参考来源

  1. ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002: 232–240. ISBN 81-7808-830-4.