标签：#圖染色

狄拉克定理

狄拉克定理解释了图染色数与完全细分图的关系。 定理描述 任何一个最小染色数大于等于4的图（\chi(G)\ge 4）均存在一个4阶完全图的细分图（K_4-subdivision）。 相关背景介绍 图染色数 对于给定的图G，存在k种颜色和一种染色方案，将图中G每一个顶点都染成k种颜色中的一种。如果染色方案满足一下条件，那么将称该染色方案为恰当的染色方案：对于图G中任意两个顶点u,v，如果uv\in E(G)，那么u,v所染成的颜色不同。 …