论文部分内容阅读
图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-圈的临界图的每个顶点以及它的邻点所关联的面的情况进行研究,并给出了适当的定义和权转移规则,反证法证明了我们的结论.