简单图的邻和可区别边染色

发布时间：2017-07-03 07:36

  本文关键词：简单图的邻和可区别边染色

  更多相关文章： 正常边染色 邻和可区别的边染色 最大平均度 平均度 平面图 权转移方法

【摘要】：对于图G=(V,E),它的正常[k]-边染色指的是G的边集E到颜色集C=[k]={1,2,...,k}的映射φ,若对于任意两条相互关联的边(?)el,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(G)d(υ)记为ad(G).最大平均度mad(G)是G的子图的平均度的最大值.本文主要证明了两个定理：定理1如果G是不含孤立边的mad(G)10/3的简单图,那么χΣ(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.
【关键词】：正常边染色 邻和可区别的边染色 最大平均度 平均度 平面图 权转移方法
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 中文摘要6-7
• 英文摘要7-9
• 第一章 绪论9-15
• §1.1 基本定义和符号9-10
• §1.2 相关概念和主要结果10-15
• 第二章 最大平均度小于10/3的邻和可区别边染色15-23
• §2.1 引理15-16
• §2.2 图G的性质16-19
• §2.3 图H及其性质19-20
• §2.4 权转移规则20-23
• 第三章 平面图的邻和可区别边染色23-39
• §3.1 定理2(1)的证明23-28
• §3.2 定理2(2)的证明28-39
• 参考文献39-43
• 致谢43-44
• 附表44

【相似文献】

中国硕士学位论文全文数据库 前1条

1 李红杰;简单图的邻和可区别边染色[D];山东大学;2016年

  本文关键词：简单图的邻和可区别边染色

  更多相关文章： 正常边染色 邻和可区别的边染色 最大平均度 平均度 平面图 权转移方法

，

本文编号：512807