论文部分内容阅读
对图论的研究已经有二百多年的历史,最早关于图论的文章是在1736年由欧拉完成的,该文章解决了著名的哥尼斯城堡七桥问题.自20世纪六十年代以来,图论得到了迅猛发展,图论方面的结果大量涌现,其中图的染色理论在图论研究中占有重要的地位,图的染色理论在最优化、计算机理论、网络设计等方面有着重要的应用.本文旨在讨论平面图的全染色. 本文讨论的图均为简单无向有限的平面图.对于一个图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染色中最小的正整数.如果一个图G的全色数xT(G)=△(G)+1,则称G为第一类图.对于G的全色数xT(G),已有的结果可以总结为: (1)对△(G)≠6的平面图,有xT(G)≤△(G)+2; (2)对△(G)≥9的平面图,有xT(G)=△(G)+1. 本文对平面图的全染色进行了讨论.全文共分三章.第一章介绍了图论中的一些基本概念,综述了当前全染色理论的主要研究成果和本文的一些主要结果.第二章我们考虑最大度较小的平面图的全染色.Behzad和Vizing分别对全染色进行了研究,提出了下面的猜想: 猜想 对任意图G,都有△(G)+1≤xT(G)≤△(G)+2.该猜想被称为全染色猜想. 本章的主要结论为: 如果平面图G的最大度△(G)≥5,并且G既不含4-圈也不含5-圈,则xT(G)=△(G)+1. 第三章中提出了图的最优全染色与强度的定义,并得到了几类平面图的全染色和与强度.