几类特殊平面图的全染色

论文摘要

图的染色问题，是图论的主要研究问题之一．图的染色一般分为边染色、点染色、全染色以及其它特定染色．本文讨论了平面图的全染色问题，证明了四个主要结论．本文讨论的图均为简单无向有限的平面图．对于一个图G=G（V（G），E（G），（?）G），V（G），E（G）分别表示其顶点集合和边的集合，（?）G为点和边的关联函数．对于顶点v∈V（G），我们用d（v）表示其度数，△（G）和δ（G）分别表示G中顶点的最大度和最小度，简记为△和δ．在图论符号中我们常略去字母G分别用V，E，v和ε代替V（G），E（G），v（G），ε（G）．若图G可以表示在平面上，并且任两条边仅在其端点处才可能相交，则称G是可平面图．图G的这种平面上的表示方法称为G的一个平面嵌入，或称平面图．一个平面图G把平面划分成若干个连通区域，这些区域的闭包称为G的面，图G所有的面构成的集合记为F．一个面f∈F所关联的边的个数（割边计算两次）称为面f的度，用d（f）或r（f）表示．若G的两个面有一条公共边，则称这两个面相邻．如果G是连通的平面图，则有|V|-|E|+|F|=2（Euler公式）．根据一定的规则将一组目标划分为不同的种类，这是数学中的一个基本方法．不同的规则决定着该组中任意一对目标是否在同一个类中．图的染色理论就是研究这类问题的一门理论，它有着相当广泛的应用背景．各种形式的日程表问题、时间表问题以及排序问题，从根本上来说都可以归结为染色问题．图G的全k染色是指至多用七种颜色，对G的顶点和边同时染色，使得相邻的两个元素（点和点，边和边，点和边）染以不同的颜色．图G的全色数xT（G）是指G的全k染色中最小的正整数k．如果一个图G的全色数xT（G）=△（G）+1，则称G为第一类图．对于G的全色数xT（G）已有的结果可以总结为：（1）对△（G）≠6的平面图，有xT（G）≤△（G）+2；（2）对△（G）≥9的平面图，有xT（G）=△（G）+1．本文讨论了几类特殊平面图的全染色．全文共分三章，第一章介绍了图论中的一些基本概念，综述了当前全染色理论的主要研究成果和本文的一些主要结果．在第二章中对3-圈至多与一个k（k=3，4，5）圈相邻的平面图的全染色得到的结论为：（1）3-圈至多与两个k（k=3，4，5）圈相邻的平面图，全染色猜想成立．另外，在第三章中给出了第一类平面图的几个充分条件：（2）设G为△（G）=6，任意两个4-圈不相邻，且无3-圈的平面图，那么XT（G）=△（G）+1．（3）设G为△（G）=7，4-圈不与k（k=3，4）圈相邻，且每点至多关联两个3-圈的平面图，那么XT（G）=△（G）+1．（4）设G为△（G）=8，3-圈至多与两个k（k=3，4，5）圈相邻的平面图，那么XT（G）=△（G）+1．

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 1.1 基本概念
• 1.2 平面图
• 1.3 染色
• 1.4 本论文的主要结果
• 1.5 本文所用的符号和基本引理
• 第二章 3-圈至多与两个k圈相邻的平面图的全染色猜想
• 第三章 第一类平面图的几个充分条件
• 3.1 △（G）=6的平面图的全染色
• 3.2 △（G）=7的平面图的全染色
• 3.3 △（G）=8的平面图的全染色
• 参考文献
• 致谢
• 攻读学位期间发表的论文
• 学位论文评阅及答辩情况表