若干图类的全染色、完备染色和选色问题研究

摘要

染色问题是图论的重要问题之一．它起源于四色问题的研究．有很强的理论意义和实际意义．目前，随着图的染色问题在现实中被广泛应用，它逐渐成为众多学者研究的重要领域之一．是图论研究中一个很活跃的课题，各类染色问题被相继提出并加以发展、应用。 本文主要研究平面规则网格——方形网格(square mesh)、六角网格(hexagonalmesh)和蜂巢网格(honeycomb mesh)的全染色问题和完备染色问题以及不含4-圈、5圈及相邻3-圈且非3-可选的平面图的选色问题。 首先，根据平面规则网格的结构特性，构造性地给出了方形网格、六角网格和蜂巢网格的全染色方案和完备染色方案，并根据所给出的全染色方案，提出了解决这三种平面规则网格全染色问题的全染色算法，这三种算法可以在多项式时间内完成对这三种平面规则网格的全染色，时间复杂度为o)(N<'2>)：证明了这三种平面规则网格的全色数为其最大顶点度数加1；方形网格、六角网格的完备色数为其最大顶点度数加3；蜂巢网格的完备色数为其最大顶点度数加4，染色方案是最优的。 其次，对于Montassier等人给出的不含4-圈、5圈及相邻3-圈且非3-可选的平面图给出了新的构造．2006年，Montassier等构造了一个包含506个顶点不含4-圈、5圈及相邻3-圈且非3-可选的平面图(Bordeaux 3-color Conjecture and3-choosability．Discrete Mathematics，306(6)(2006)：573-579)，推翻了Bordeaux3-色猜想：所有不含5-圈和相交3-圈的平面图是3-可选的．本文构造了一个具有相同性质且包含更少顶点的平面图，这个平面图仅包含380个顶点，目前是含最少点的不含4-圈、5圈及相邻3-圈且非3-可选的平面图。

目录

文摘

英文文摘

大连海事大学学位论文原创性声明和使用授权说明

第1章 绪论

1.1引言

1.2全染色问题的发展及现状

1.3完备染色问题的发展及现状

1.4选色问题的发展及现状

1.5本文的研究内容与安排

第2章 基本概念及预备知识

2.1基本概念与记号

2.2几种典型的图染色

2.3全染色的主要结论

2.4完备染色的主要结论

第3章 网格的全染色及完备染色

3.1平面网格的坐标系

3.1.1方形网格的坐标系

3.1.2六角网格的坐标系

3.1.3蜂巢网格的坐标系

3.2平面网格的全染色方案

3.2.1方形网格的全染色方案

3.2.2六角网格的全染色方案

3.2.3蜂巢网格的全染色方案

3.3平面网格的全染色算法

3.3.1方形网格的全染色算法

3.3.2六角网格的全染色算法

3.3.3蜂巢网格的全染色算法

3.4平面网格的完备染色方案

3.4.1方形网格的完备染色方案

3.4.2六角网格的完备染色方案

3.4.3蜂巢网格的完备染色方案

第4章 更小的不含4-圈、5圈及相邻3-圈的非3-可选图

4.1定义及相关结果

4.2不含4圈、5-圈和相交3-圈的平面图

第5章 结束语

5.1本文研究的主要工作

5.2待研究的问题

参考文献

攻读学位期间公开发表论文

致 谢

研究生履历