NOIP 提高 2015 第一轮 第 14 题：对图 G 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 G 的一个正

题目

对图 $G$ 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 $G$ 的一个正常着色。正常着色图 $G$ 所必需的最少颜色数，称为 $G$ 的色数。那么下图的色数是（   ）。

选项

• A. 3
• B. 4
• C. 5
• D. 6

答案

A

题解

考点定位

本题考「图的色数」,对应大纲 4.3.4 图着色（难度【4】）。

解题过程

按原卷图（含奇圈结构）：需要 3 色正常着色（含三角形的图至少 3 色，且该图可 3 着色）。

选 A。

易错提醒

① 含奇圈 ⇒ 色数 ≥3；② 色数=2 ⟺ 二分图。