例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点同色? 在同构意义下着色是唯一的? (着色导出的划分是同构的)