论文摘要
如果存在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）从而得到矛盾.
论文目录
文章来源
类型: 硕士论文
作者: 牛琳
导师: 李相文
关键词: 强边染色,强边染色数,定理
来源: 华中师范大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 华中师范大学
分类号: O157.5
总页数: 30
文件大小: 1415K
下载量: 19