平面图的放松均匀染色与强边染色

论文摘要

设G=（V,E）,图G的一个正常的k-点（边）染色就是k种颜色对点（边）的分配,使得任意相邻的点（边）分配到不同的颜色.一个正常的点染色如果每个色类的大小至多差1,称染色是均匀的.图G的均匀染色数是使得图G是均匀m-可染的最小的整数m,用χeq（G）表示.一个放松的k-染色是对点的k-染色使得每个点与至多一个邻点染相同的颜色.图G的一个放松均匀k-染色（简记ED-k-染色）是图G的点集的一个放松的k-染色使得任意两个色类的大小至多差1.图G的ED-色数是使得G是ED-m-可染的最小整数m,记为χed（G）.图G的ED-染色阈值是使得图G对任意n≥ m都是ED-n-可染的最小整数m,记为χed*（G）.本文我们证明最小度至少2且围长至少为8的平面图有χed*（G）≤4.图的强边染色是一种正常边染色.要求任何长至多为3的路上的边都染不同的颜色.使得图有一个强边染色的最小颜色数称为图的强边色数.用χ’s（G）表示.Faudree等人证明任意最大度为△的平面图有χ’s（G）≤ 4△+4.那么△=4时.χ’s（G）≤ 20.最近,Wang等人证得其强边色数不超过19.本文中我们证明不含带弦5-圈和梯子图L3的平面图是18-强边可染的.并且,对最大度为4的平面图,若它是一个非18-强可染的边数极小图.则它一定不存在至多含三条边的非平凡边割.本论文共分为四章.主要研究了平面图的放松均匀染色问题和强边染色问题.第一章,我们主要介绍了图染色问题的背景及意义,给出了本中用到的基本概念与符号,阐述了放松均匀染色和强边染色问题的研究现状,及本文的主要结果.第二章,我们研究了围长至少为8的平面图的放松均匀染色,证明其对任意m≥4都是ED-m-可染的.第三章,我们研究了最大度为4的平面图18-强边染色,给出了一个充分条件.此外,基于图的k-边割,我们讨论了非18-强边可染的极小图的结构.第四章,我们给出了可进一步研究的问题.

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
•   1.1 基本概念与符号
•   1.2 图的放松均匀染色问题的研究现状
•   1.3 图的强边染色问题的研究现状
•   1.4 本文的主要结果
• 第二章 放松均匀染色问题
•   2.1 预备知识和主要结果
•   2.2 极小反例的结构
•   2.3 定理2.1.2的证明
• 第三章 强边染色问题
•   3.1 一类18-强边可染的△=4的平面图
•   3.2 非18-强边可染的极小反例的结构
• 第四章 可进一步研究的问题
• 参考文献
• 攻读学位期间完成、发表或提交的学术论文
• 致谢

文章来源

类型: 硕士论文

作者: 李明

导师: 张霞

关键词: 放松均匀染色,强边染色,定理,边割,权转移

来源: 山东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东师范大学

分类号: O157.5

DOI: 10.27280/d.cnki.gsdsu.2019.000036

总页数: 51

文件大小: 2276K

下载量: 20