狄拉克定理

若圖的染色數≥4, 則包含K₄的細分圖

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

定理描述

编辑

任何一个最小染色数大于等于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.