定理127 定理127:对图G进行X(G)-着色设 v= LVVEV(G八∨着颜色门,=1,2,…,(G), 则∏=V12…4(是的划分# 定理127:对图G进行X(G)-着色设 R={4u>|ueV(G)八u,着同样颜色},则 R是VG)上等价关系,# 鲁说明:V中的点构成独立集” 《集合论与图论》第25讲
《集合论与图论》第25讲 6 定理12.7 定理12.7: 对图G进行χ(G)-着色,设 Vi={v|v∈V(G)∧v着颜色i}, i=1,2,…, χ(G), 则Π={V1,V2,…,Vχ(G)}是V(G)的划分. # 定理12.7’:对图G进行χ(G)-着色,设 R={<u,v>| u,v∈V(G)∧u,v着同样颜色}, 则 R是V(G)上等价关系. # 说明: Vi中的点构成“独立集”
x(G)上界 定理125:X(G)≤△(G)+1 证明:WVeV(G,Te(v)={u|(u)EE(G) c)△(G),给I)中顶点着色至多需 要A(G种颜色,所以至少还剩一种颜色可 用来给v着色.# 定理126(Boks:若G连通非完全图Kn (≥3)非奇圈,则(G)≤△(G).# 说明:n=1G=K1n=2:连通→G=K 《集合论与图论》第25讲
《集合论与图论》第25讲 7 χ(G)上界 定理12.5: χ(G) ≤ Δ(G)+1 证明: ∀v∈V(G), ΓG(v)={ u | (u,v)∈E(G) }, |ΓG(v)|≤Δ(G), 给ΓG(v)中顶点着色至多需 要Δ(G)种颜色, 所以至少还剩一种颜色可 用来给v着色. # 定理12.6(Brooks): 若G连通非完全图Kn (n≥3)非奇圈, 则χ(G) ≤ Δ(G). # 说明: n=1⇒G=K1, n=2: 连通⇒G=K2
例121( Petersen图) 例121: Petersen图x=3 解1:由 Brooks定理,x≤A=3.又图中有奇 圈,x23.所以x=3.# 解2:存在如下3-着色,xA=3又图中有 奇圈,X≥3.所以x=3.# 思考题:至少有3点同色? 在同构意义下着色是唯一的? (着色导出的划分是同构的) 《集合论与图论》第25讲
《集合论与图论》第25讲 8 例12.1(Petersen图) 例12.1: Petersen图χ=3. 解1: 由Brooks定理, χ≤Δ=3. 又图中有奇 圈, χ≥3. 所以χ=3. # 解2: 存在如下3-着色, χ≤Δ=3. 又图中有 奇圈, χ≥3. 所以χ=3. # 思考题: 至少有3点同色? 在同构意义下着色是唯一的? (着色导出的划分是同构的)
地图 地图:连通无桥平面图的平面嵌入及其所 有的面称为(平面)地图 国家:平面地图的面 秦相邻:两个国家的公共边界至少有一条公 共边 k-面着色,k色地图,面色数x(G) 《集合论与图论》第25讲
《集合论与图论》第25讲 9 地图 地图: 连通无桥平面图的平面嵌入及其所 有的面称为(平面)地图 国家: 平面地图的面 相邻: 两个国家的公共边界至少有一条公 共边 k-面着色, k-色地图, 面色数χ*(G)
面着色与对偶图点着色 婚定理1213:地图G可k-面着色⊙对偶图 G*可k-着色.# 婚定理1214连通无环平面图G可K面着色 台对偶图G*可K着色.# 研究平面图面着色◇→研究平面图点着色 《集合论与图论》第25讲
《集合论与图论》第25讲 10 面着色与对偶图点着色 定理12.13: 地图G可k-面着色 ⇔ 对偶图 G*可k-着色. # 定理12.14: 连通无环平面图G可k-面着色 ⇔ 对偶图G*可k-着色. # 研究平面图面着色⇔研究平面图点着色