论文部分内容阅读
图G的k-边染色是用k种颜色对图G的边集合的元素进行着色，使得相邻的两条边染不同的颜色，即存在一个映射ψ:E(G)→{1，2，…，k}，对G中任意两条相邻的边e1和e2，有ψ(e1)≠ψ(e2).图G的边色数，用x(G)表示，是使G存在k-边染色的最小整数k.Vizing定理指出:对于任意简单图G，我们有x(G)=△(G)或△(G)+1.如果x(G)=△(G)，图G称为第一类的，如果x(G)=△(G)+1，图G称为第二类的.Vizing证明了△≥8的平面图是第一类的，并且提出著名的Vizing猜想:每个最大度不小于6的平面图是第一类的.对△=7的情形已由Sanders和Zhao以及Zhang独立证明.因此，Vizing猜想只剩下△=6的情形还没有证明.Ni证明了最大度为6且不含弦-k-圈（4≤k≤7）的平面图是第一类的. 我们证明了:最大度为6，且不含弦-8-圈的平面图是第一类的.利用反证法，假如存在最大度为6，且不含弦-8-圈的平面图G是第二类的，不妨设G是临界图，对任意x∈V(G)∪F(G)，定义权函数为ch(x)=d(x)-4，得到所有顶点和面上的权值之和为-8，并设置了权值转移规则，在权值重新分配的过程中，所有顶点和面的权值之和保持不变，对所有的顶点和面上的权值进行重新分配后得到的新权值定义为ch，如果对任意的x∈V(G)∪F(G)，都有ch(x)≥0，就会得到矛盾:0≤∑x∈V(G)∪F(G)ch(x)=∑x∈V(G)∪F(G) ch(x)=-8＜0，从而证明不存在这样的反例.我们发现:对于最大度为6，且不含弦-8-圈的临界图，存在关联3-面的个数较多且关联6个面的度数之和较小的6-点，在权值转移的过程中，这类6-点传递给它的邻点以及它关联的3-面的权值之和大于这类6-点从它所关联的面上得到的权值之和，我们通过对这类6-点的某些邻点的结构进行研究，发现这些邻点所关联的面的度数较大，因此，在设置权转移规则时，可安排这类6-点从它的某些邻点上得值.权值重新分配后，我们验证了任意顶点和面上的权值都不小于0，反证法证明了我们的结论. 2≤△≤5的平面图既有第一类图，也有第二类图，Ni证明了:最大度为5且不含弦-4-圈和弦-k-圈（k=5，6）的平面图是第一类的.我们证明了:最大度为5且不含弦-4-圈和弦-7-圈的平面图是第一类的.我们分别对最大度为5且不含弦-4-圈和弦-7-圈的临界图的每个顶点以及它的邻点所关联的面的情况进行研究，并给出了适当的定义和权转移规则，反证法证明了我们的结论.