具有稀疏三角形的可平面图的3列表可染性

摘要

如果一个图G能够嵌入到平面内，使得边仅在端点处相交，则称G是可平面图.两个圈的距离是指两个圈上的点的距离的最小值.在本文中，3圈又叫做三角形. 对于一个可平而图G=(V, E)，若存在一个映射φ：V→(1，2，…k)，满足，对()uv∈E，有φ(u)≠φ(v)，则称φ是G的一个顶点k染色.若G存在一个顶点k染色，则称G是k可染的.使得G是k可染的最小正整数k，叫做G的染色数，用χ(G)表示.给图G的每一个顶点v分配一张色表L(v)，称L={L(v)｜()v∈V)是G的一张色列表.设L是G的一张色列表，若存在一个映射φ，满足(1)()V∈V，有φ(V)∈L(V)；(2)()uv∈E，有φ(u)≠φ(v)，则称G是L可染的.若对G的每一张满足｜L(v)｜≥k，()v∈V)的色列表L，G都是L可染的，则称G是k列表可染的.使得G是k列表可染的最小正整数k，叫做G的列表染色数，用ch(G)表示. 在1996年，Gutner证明了：确定一个平面图是3列表可染的是NP困难的.这样，研究平面图是3列表可染的充分条件就有意义了. 本文主要关注的是具有稀疏三角形的平面图的3列表可染性，主要证明了以下几个结论： 1.每一个不含4，6，8圈且任意两个三角形的距离至少为2的可平面图是3列表可染的. 2.每一个不含4，7，9圈且任意两个三角形的距离至少为3的可平面图是3列表可染的. 3.每一个不含4，8，9圈且任意两个三角形的距离至少为3的可平面图是3列表可染的.

目录

文摘

英文文摘

声明

1 绪论

1.1 基木概念

1.2平面图3列表染色问题的研究概况与本文的研究工作

2 不含4，6，8圈的平面图的3列表可染性

2.1 结构性质

2.2 定理2.1的证明

3 不含4，7，9圈的平面图的3列表可染性

3.1 极小非3列表可染图的结构

3.2不含4，7，9圈的平面图的结构性质

3.3 定理3.1的证明

4 不含4，8，9圈的平面图的3列表可染性

4.1 极小非3列表可染图的结构

4.2不含4，8，9的平面图的结构性质

4.3 定理4.1的证明

参考文献

在学期间的研究成果及发表的论文

致谢