几类特殊平面图的全染色

摘要

图的染色问题，是图论的主要研究问题之一.图的染色一般分为边染色、点染色、全染色以及其它特定染色.本文讨论了平面图的全染色问题，证明了四个主要结论. 本文讨论的图均为简单无向有限的平面图.对于一个图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染色是指至多用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的平面图的全染色

参考文献

致 谢

攻读学位期间发表的论文