【知识总结】 边染色、点染色和面染色

边染色

相关概念

• 边染色
  • ：色为的边集
• 边正常染色：相邻的边不同色
• 边色可染的： 能找到一个边正常染色
• 边色数：
  • 边色可染的最小
  • 记作
• 只考虑无环图，可以有重边

边色数的性质和意义

• 和匹配的联系：
  • 至少要被划分成个匹配
  • 如果能被划分为个匹配，则

最佳边k染色

• 对于边染色，用表示顶点出现的色数
• 若，则称是的一个改进
• 不能改进的边染色称作最佳边染色（未必是边正常染色）

Vizing定理

对于简单图，

简单图的分类

• 第一类图：
• 第二类图：

二部图的边色数

• 对于二部图，
• 二部图的边正常染色算法
  • 正则二部图有个边不重的完美匹配
  • 算法思路
    • 将二部图扩展成正则二部图
    • 反复的求最大匹配，即完美匹配，染色后从图中删去
    • 忽略添加的顶点和边
  • 二部图边染色复杂度：目前最快的算法是；
  • 一般简单图的边染色：多项式时间内可以做到染色

点染色

相关概念

• 染色
  • ：色为的顶点集
• 正常染色：相邻的顶点不同色
• 色可染的： 能找到一个正常染色
• 色数：
  • 色可染的最小
  • 记作

色数的性质和意义

• 和点独立集的联系：
  • 至少要被划分成个点独立集
  • 如果能被划分为个点独立集，则

色临界图及其性质

• 临界的：的极小图
• 色图一定包含一个临界子图
• 色临界图一定是连通的简单图
• 对于临界图中的任一顶点，能找到一个正常染色使得的色独一无二且与其他种色都相邻
• 临界图满足
• 对于临界图中的任一边，的任一正常染色都使得的两个端点同色
• 色临界图的点割集不是团（两两相邻的顶点子集）
• 每个色临界图都是块（无割点的连通图）
• 色临界图若有2-点割集，则和不相邻

色数的界和正常染色算法

贪心算法一

• 假设可以染的色为
• 对于顶点按任意序染色，总选择不冲突的下标最小的色
• 最多需要种颜色

贪心算法二

• 假设可以染的色为
• 对于顶点按度降序染色，总选择不冲突的下标最小的色
• 初期较小，后期较小，因此总体较小

定理

除完全图和奇圈以外的连通简单图满足

其他

• 对于，判断一个图是否色可染是NP-完全问题
• 一般意义上的求色数更是问题
• 找到一个近似比为常数的近似算法同样困难

面染色

相关概念

• 面染色
• 面正常染色：边界有公共边的面不同色
• 面色可染的
• 面色数

五色定理

• 定理：对于任何平面图,
• 推论：由对偶图都是平面图，故平面图一定是面5色可染的

四色猜想

• 猜想：对任何平面图，
• 三角剖分平面图：每个面的度数都为3的简单平面图
• 构形：每个内部面的度数都为3的简单平面图
• 极小反例：
  • 的简单平面图中阶最小的一个
  • 不失一般性，设其为三角剖分平面图，如果不是也可以加边使之成为三角剖分平面图，且还是极小反例。
• 不可免集：构形的集合，任何一个极小反例至少包含其中一个构形
• 如果找到一个不可免集，其中每个构形都不可能出现在极小反例中，称作可约的，则出现了矛盾，因此极小反例不存在，四色猜想得证。