无四圈环面图的4-选色问题

论文摘要

对图G的每个顶点v，令L（v）表示可用于点v的颜色列表，则给定图G的顶点上的一个颜色列表集合L={L（v）|v∈V（G）}。一个列表染色是一个真染色f，它使得f（v）∈L（v）对所有v均成立。如果对所有顶点v，只要|L（v）|≥k，均存在一个列表染色，则称图G是k—可选色的或简称为k-可选的，并记列表色数、选择数或可选数χl（G）=min{k|图G是k—可选色的}。没有边缘而且可以剖分成有限个多边形的曲面称为闭曲面。球面是最简单的闭曲面。在球面上添加一些手柄得到了新的表面，其亏格是所添加的手柄的个数。我们将亏格为γ的表面记为Sγ。图G的亏格是使得G能够嵌入到Sγ上的最小γ值，使得它的边仅在顶点相交。亏格是0、1的图分别称为平面图、环面图。在文献[18]中，作者证明了无4—圈的平面图是4—可选的，本文在此基础上证明：定理：无4—圈的环面图是4—可选的。

论文目录

• 摘要
• Abstract
• 前言
• 第一章 基本概念及已有结论
• 1.1 图论基本概念与符号
• 1.2 图的染色定义
• 1.3 图的列表染色定义
• 1.4 与本文有关的一些已知结果
• 1.5 本文的主要结果
• 第二章 定理证明
• 2.1 可约构形
• 2.2 权传递规则
• 2.3 点,面的新权重计算及引理2.1证明
• 2.4 结论证明
• 第三章 可以进一步研究的问题
• 参考文献
• 致谢