图的松弛强边染色

论文摘要

令G是一个有限简单图且k是正整数.用V（G）,E（G）以及F（G）分别表示图G的顶点集,边集以及面集,简记为V,E和F.若存在映射π:E{1,2,...,k},使得E中任意两条相邻边e和e’,都有π（e）≠π（e’）,则称π是图G的一个正常的k-边染色,并称G是正常k-边可染的.图G的边色数χ’（G）定义为使得G是正常k-边可染的最小正整数k的值.若存在映射π:E（G）-→ {1,2,...,k},使得E中任意两条距离至多为2的边e和e’,都有π（e）≠π（e’）,则称π是图G的一个强边k-染色,并称G是强边k-可染的.图G的强边色数χs’（G）定义为使得G是强边k-可染的最小正整数k的值.给定两个非负整数s和t.若存在映射π:E（G）-→ {1,2,...,k}使得G中任意一条边e,满足其颜色π（e）在它的1-邻域中至多出现s次,且在它的2-邻域中至多出现t次,则称π是G的一个（s,t）-松弛强边k-染色,并称G是（s,t）-松弛强边k-可染的.图G的（s,t）-松弛强边色数χ（s,t）’(G定义为使得G是（s,t）-松弛强边k-可染的最小正整数k的值.给图G中的每条边e配置一个颜色集合L（e）,记L={L（e）| e ∈E}.如果存在一种正常边染色π,使得π（e）∈ L（e）,那么称G是L-边可染或称G有一个L-边染色.若对所有的e ∈E（G）,对于任意配置的列表L,其中|L（e）| ≥k,G都是L-边可染的,则称G是k-边列表可染的.我们把使得G是k-边列表可染的最小正整数k的值定义为G的边列表色数,记作ch’（G）.若存在一个强边染色π,使得对每条边e都有π（e）∈ L（e）,则称G是强边L-可染的.同时染色π被称作G的一个强边L-染色.类似地,当|L（e）| ≥ k且G是强边L-可染的,称G是强边列表k-可染的.G的强边列表色数定义为使得G是强边列表k-可染的最小正整数k的值,记作chs’（G）.若存在一个（s,t）-松弛强边染色π,使得对每条边e都有π（e）∈ L（e）,则称G是（s,t）-松弛强边L-可染的.同时染色π被称作G的一个（s,t）-松弛强边L-染色.类似地,当|L（e）| ≥ k且G是（s,t）-松弛强边L-可染的,称G是（s,t）-松弛强边k-列表可染的.G的（s,t）-松弛强边列表色数定义为使得G是（s,t）-松弛强边k-列表可染的最小正整数k的值,记作ch（s,t）’（G）.2017年,He和Lin首次提出了图的（s,t）-松弛强边染色问题.近年来,图的（s,t）-松弛强边染色问题引起了国内外研究者的极大关注.注意到,若s=t=0时,对应为人们熟知的强边染色问题.因此,（st）-松弛强边染色问题是强边染色的一种自然推广.本学位论文主要围绕此课题展开研究.我们将给出在围长限制条件下的平面图的（1,0）-松弛强边列表染色的一些结果.论文框架结构及内容如下:在第一章中,我们将先给出本文用到的一些基本概念,然后简述相关领域的研究现状和本文的研究结果.在第二章,第三章和第四章中,我们均运用反证法,通过构造极小反例,运用色延拓技巧以及经典的权转移方法,分别证明了以下三个结果:（1）如果G是一个围长至少为6的平面图,那么ch’(1,0（G）≤ 3△（G）-1.（2）如果G是一个围长至少为7的平面图,那么ch’(1,0（G）≤ 3△（G）-2.（3）如果G是一个围长至少为9的平面图,那么ch’(1,0（G）≤ 3△（G）-3.

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 基本概念
•   1.2 图的强边染色研究现状
•   1.3 图的（s,t）-松弛强边染色研究现状
•   1.4 本文的主要结果
• 第二章 围长至少为6的平面图的（1,0）-松弛强边列表染色
•   2.1 符号说明
•   2.2 结构性质
•   2.3 权转移过程
• 第三章 围长至少为7的平面图的（1,0）-松弛强边列表染色
•   3.1 定理3.2的证明过程
•   3.2 定理3.3的证明过程
• 第四章 围长至少为9的平面图的（1,0）-松弛强边列表染色
•   4.1 定理4.2的证明过程
•   4.2 定理4.3的证明过程
• 参考文献
• 攻读学位期间取得的研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 林凯

导师: 陈敏

关键词: 平面图,强边染色,松弛强边染色,松弛强边列表染色,围长

来源: 浙江师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江师范大学

分类号: O157.5

DOI: 10.27464/d.cnki.gzsfu.2019.000804

总页数: 62

文件大小: 2793K

下载量: 16