论文部分内容阅读
对于图G=(V, E),它的正[k]-边染色指的是G的边集E到颜色集C=[k]={1,2,…,k}的映射ψ,若对于任意两条相互关联的边(∨)e1,e2∈E(G)有ψ(e1)≠ψ(e2),则称ψ是G的正常[k]-边染色,我们用x(G)表示使得G有正常[k]-边染色的最小整数k.给定G的正常[k]-边染色ψ,Sψ(v)表示与v相邻的边的权值和,任意uv∈E(G),有Sψ(u)≠Sψ(v),称染色ψ为图G的邻和可区别的[k]-边染色.我们用x∑(G)表示使得G有邻和可区别的[k]-边染色的最小整数k.G的平均度为Σv∈V(G)d(v)/|V(G)|,记为ad(G).最大平均度mad(G)是G的子图的平均度的最大值.本文主要证明了两个定理: 定理1如果G是不含孤立边的mad(G)<10/3的简单图,那么x∑(G)≤k,其中k=max{△(G)+3,11}. 定理2(1)设G是最大度为△,围长为g的正常平面图,如果g≥5,则x∑(G)≤k,其中k=max{△(G)+3,10}. (2)设G是最大度为△且不含4-圈的正常平面图,则x∑(G)≤k,其中当△(G)≠10时,k=max{△(G)+3,13},当△(G)=10时,k=max{△(G)+3,14}=14. 本文主要内容具体分为三章展开: 第一章,首先介绍了本文用到的基本定义和符号,其次介绍了相关概念和已得到结果,最后给出了本文要证明的两个定理. 第二章,我们利用权转移方法证明了定理1. 第三章,我们利用欧拉原理及权转移规则构造反例证明了定理2.