论文部分内容阅读
本文所考虑的图都是有限简单图.我们用V(G)，E(G)，F(G)，△(G)，δ(G)和g分别表示平面图G的顶点集，边集，面集，最大度，最小度及围长.对任何一点v∈V，我们把与v相邻的所有点的集合记作N（v），用d(v)=|N(v)|代表v的度数.一个k-圈是长度为k的圈，其中3-圈也称作三角形.长度不超过5的圈称为短圈.图G的正常k-全染色是指用k种颜色对V(G)∪E(G)中的元素进行染色，使得相邻的或者相关联的两个元素染不同的颜色.使得图G存在正常的k-全染色的最小正整数k称为G的全色数，记作x"(G).如果我们只对图G的顶点或者边进行染色，那么就可以分别得到图G的点色数x(G)和边色数x(G).显然，x"(G)≥△+1.Behzad和Vizing各自独立提出下面这个著名猜想:对任意图G，△(G)+1≤x"(G)≤△+2. 对于一般图来讲，该猜想在最大度为△≤5的图中已被证明是成立的.对于平面图而言，仅剩下△=6的情形是需要验证成立的. 我们利用“充放电”的方法，求得了几类有限制条件的平面图的全色数. 首先讨论了不含相交短圈的情形，得到如下结论: 定理1假设G是最大度为△(G)≥7的平面图.如果3-圈与3-圈不相交，那么它的全色数x"(G)=△+1. 定理2假设G是最大度为△(G)≥7的平面图.如果3-圈与4-圈不相交，那么它的全色数x"(G)=△+1. 定理3假设G是最大度为△(G)≥7的平面图.如果5-圈与5-圈不相交，那么它的全色数x"(G)=△+1. 然后讨论了不含带弦6-圈的平面图的染色问题，得到如下结论: 定理4假设G是最大度为△(G)≥7的平面图.如果G不含带弦6-圈，那么它的全色数x"(G)=△+1. 继而讨论了最大度不大于5的平面图的全染色问题，得到如下结论: 定理5假设G是最大度为△，围长为g的平面图，且存在一个整数t(＞g)使得G不含有长度从g+1到t的圈.如果(a)（△，g，t）=(5，4，6)或者(b)（△，g，t）=(4，4，17)，那么它的全色数x"(G)=△+1. 定理6假设G是最大度为3，围长为g，每个顶点至多关联一个g-圈的平面图，且存在一个整数t(＞g)使得G不含有长度从g+1到t的圈.如果G满足以下条件之一，那么它的全色数x"(G)=△+1.(a)g=5且t≥29，(b)g=6且t≥17，(c)g=7且t≥13;(d)g=8且t≥11，(e)g=9且t≥10. 最后，从度和的角度研究了平面图的全染色问题.令s△=min{d(u)+d(v)+d(w)|uvw是G中的任意三角形}及δ△=min{d(u)，d(v)，d(w)|uvw是G中的任意三角形}. 定理7假设G是最大度为△≥7的平面图.如果s△≥18且δ△≥6，那么它的全色数x"(G)=△+1. 定理8假设G是最大度为△≥8的平面图.如果s△≥19且δ△≥5，那么它的全色数x"(G)=△+1. 本文讨论的另一个问题是列表染色.对于图G的每一条边e，我们都给定一个颜色集合L(e)，那么这个映射L就称为图G的一个边安排.如果图G存在边染色ψ使得对任意边e∈E(G)，都有ψ(e)∈L(e)，则称图G是L-边可染的.对于图G的任意一个满足条件|L(e)|≥k的边安排L，其中e∈E(G)为G的任意一条边，如果G都是L-边可选择的，那么就称图G是k-边可选择的.使图G是k-边可选择的最小正整数k称为图G的列表边色数，记作xl(G). 类似地，我们可以给出图G的列表色数Xl(G)和列表全色数X"l(G)，它们分别是把上述边染色换为对图G的顶点或者顶点和边进行染色.从上述定义中我们马上可以得到下列关系:xl(G)≥x(G)≥△，x"l(G)≥x"(G)≥△+1. 本文主要讨论了平面图的列表染色.主要结论有: 定理9假设G是最大为△(G)≥8的平面图.如果3圈与k圈不相邻k∈{4，5}，那么xl(G)=△且x"l(G)=△+1. 本文讨论的最后一个问题是无圈全染色.一个图G的正常全染色被称为无圈全染色，如果它能够使得G中的每个圈所关联的点或边上至少出现4种颜色.图G的无圈全色数x"a(G)是使得图G存在一个无圈全染色的最小正整数k.无圈全染色问题是由孙向勇、吴建良提出，并给出以下猜想:对任意图G，△(G)+1≤x"a(G)≤△(G)+2. 本文研究了平面图的无圈全染色.我们给出了有关上述猜想的的主要结果: 定理10假设G是最大度为△≥6的平面图.如果3-圈与4-圈不相交，那么它的无圈全色数x"a(G)≤△+2. 定理11假设G是最大度为△≥7的平面图.如果3-圈与3-圈不相交，那么它的无圈全色数x"a(G)≤△+2. 定理12假设G是最大度为△≥7的平面图.如果短圈i-圈与j-圈(i≠j）不相邻，那么它的无圈全色数x"a(G)≤△+2. 定理13如果G是最大度为△≥9的平面图，那么它的无圈全色数x"a(G)≤△+2.