基本信息

---

下载

文档摘要

---

摘要

图的染色理论起源于四色猜想，已经发展成图论研究的一个重要分支，根据

染色方式的不同，已有近千种染色出现。本文主要研究图的无圈点染色和无圈边

染色问题。

图的一个无圈-点染色是一个正常点染色，并且使得中不含有双色圈。颜

色数的最小值称为图的无圈点色数，用()表示。类似地，可以定义无圈-

边染色和无圈边色数′()。1973年Gru?nbaum提出了无圈点染色的概念。1978

年，