平面图的强边染色

平面图的强边染色

论文摘要

如果存在G的边集到颜色集的一个映射φ:E(G)→{1,2,...,k},使得对任意两条距离不大于2的两条边e,e’染不同的颜色,即φ(e)≠φ(e’),称图G是fk-强边染色.定义图G的强边染色数为xs’(G)=min{k|图G有fk-强边染色}.本文通过研究图G的强边染色与点度数的关系,证明了以下定理:最大度为3的简单图G,如果g(G)≥ 6,任意的7--圈不邻接9--圈并且任意的8-圈不邻接8-圈,它的强边染色数至多为8.要证明这个定理,首先我们研究的图都是有限的简单图,假设图G是|V(G)|+|E(G)|最小的反例,如果我们能证明最小反例不存在,那么我们的定理就能够证明.证明该定理主要分为两部分:第一部分是通过证明图G不存在的结构来确定图G的结构.第二部分是通过给点面赋权值,分别为μ(v)=2d(v)-6,μ(f)=d(f)-6,由欧拉公式得到初始总权值 ∑v∈V(G)∪F(G)μ=-12.通过一定规则的权转移后,使得所有点面的权值均大于等于0,即(?)μ(x)=-12.(0.1)从而得到矛盾.

论文目录

  • 摘要
  • Abstract
  • 第一章 绪论
  •   1.1 引言
  •   1.2 本文研究内容与安排
  • 第二章 预备知识
  •   2.1 基本概念与符号表示
  •   2.2 相关研究的发展与现状
  • 第三章 可约结构
  • 第四章 权转移过程
  •   4.1 图G是2-连通的
  •   4.2 图G不是2-连通的
  • 第五章 总结展望
  • 参考文献
  • 致谢
  • 文章来源

    类型: 硕士论文

    作者: 牛琳

    导师: 李相文

    关键词: 强边染色,强边染色数,定理

    来源: 华中师范大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 华中师范大学

    分类号: O157.5

    总页数: 30

    文件大小: 1415K

    下载量: 19

    相关论文文献

    标签:;  ;  ;  

    平面图的强边染色
    下载Doc文档

    猜你喜欢