1. 第九章 平面图及其着色

1.1. 9.4 图的顶点着色

1.1.1. 3

设 $G$ 是一个有 $p$ 给顶点的 $d$ - 正则图。证明： $\chi(G) \geq p/(p - d)$ 。

1.1.2. 5

设 $G$ 是一个 $(p, q)$ 图，证明：

$$\chi (G) \geq p^2 / (p^2 - 2q)$$

1.1.3. 7

证明：每个哈密顿平面图都是 $4$ - 可着色的。