顶点着色-基本概念
•
K 可着色: G 的一个 k 顶点着色是指 k 种颜色 1,2,…,k 对于 G 各
顶点的一个分配,如果任意两个相邻顶点都分配到不同的颜色,
则称着色是正常的。换句话说,无环图 G 的一个正常 k 顶点着色是
把 V 分成 k 个(可能有空的)独立集的一个分类 (
V
1,
V
2,…,
Vk
) 。
当 G 有一个正常 k 顶点着色时,就成 G 是 k 顶点可着色的。
•
G 的色数 X ( G )是指 G 为 k 可着色的 k 的最小值,若 X ( G ) =k ,
则称 G 是 k 色的。
•
事实上,如果我们将同色的顶点列入一个顶点子集,那么求 X
( G )就转为求满足下列条件的最少子集数 k :
( 1 )两两子集中的顶点不同;
( 2 )子集中的两两顶点不相邻。
显然有: ( i )若 G 为平凡图,则 X ( G ) =1 ;
( ii )若 G 为偶图,则 X ( G ) =2
( iii )对任意图 G ,有 X ( G )≤ Δ+1 (这里 Δ 表示为
顶点数最大值)