图的强边染色和星边染色

论文摘要

本文主要研究图的强边染色和星边染色.图G的一个正常k-边染色是指一个映射φ:E（G）→{1,2,...,k},使得对任意两条相邻的边e1,e2都有φ（c1）≠φ（c2）.若图G有一个正常k-边染色,那么就称G是k-边可染的.图G的边色数是使G有一个正常k-边染色的最小非负整数k,用χ’（G）表示.若在图G的一个正常k-边染色φ下,任意两条距离至多是2的边染不同的颜色,则称φ是G的一个强k-边染色.若图G有一个强k-边染色,我们称G是强k-边可染的.图G的强边色数是使G是强k-边可染的最小非负整数k,用χ’s（G）来表示.若在图G的一个正常k-边染色φ下,G中不存在长度为4的双色路或双色圈,则称φ是G的一个星k-边染色,即G中任意长度为4的路或圈至少用三种颜色染色.若图G有一个星k-边染色,那么就称G是星k-边可染的.图G的星边色数是使G是星k-边可染的最小非负整数k,用χ’st（G）表示.根据定义,可知χ’s（G）≥χ’st（G）≥χ’（G）≥ △.1983 年,Fouquet 和 Jolivet 提出了强边染色的概念.1989 年,Erdos 和 Nesetril提出猜想:对任意的图G,若△为偶数,则χ’s（G）≤5/4△2;若△为奇数,则χ’s（G）≤5/4△2-1/2△+1/4.目前,当△ ≤ 3时,猜想已经被验证成立;但当△ ≥ 4时,猜想尚未解决.1990年,Faudree等人研究了平面图的强边染色,并证明了对△ ≥ 3的平面图G有χ’s（G）≤ 4χ’（G）≤ 4△+4.同时,他们构造了一类最大度△ ≥ 2且χ’s（G）=4△-4的平面图.2013年,Hocquard等人证明了每个△ ≥ 3的外平面图G满足χ’s（G）≤ 3△一3,并且他们指出这个上界是紧的.Liu和Deng于2008年提出了星边染色的概念.同时,他们证明了对△ ≥ 7的简单图G有χ’st（G）≤[16（△-1）3/2].2016年,Bezegova等人研究了外平面的星边色数并证明:若G是一个外平面图,则有χ’st（G）≤[1.5△]+12.更进一步,他们猜想:对每个△ ≥ 3的外平面图G都有χ’st（G）≤[1.5△]+1.本学位论文主要研究了最大度为4的平面图、外平面图、弦图的强边染色问题,平面图、无K4-子式的图、外平面图、最大度为4的图的星边染色问题,共分成六章.在第一章中,我们给出了本文所涉及的基本概念和相关领域的研究现状,并呈现了本文的主要结果.在第二章中,我们研究了最大度是4的平面图的强边染色,证明了每个△=4的平面图是强19-边可染的,这个结果改进了这类图的强边色数的已知上界20.在第三章中,我们研究了外平面图的强边染色,刻画了 △ ≥ 3且达到强边色数上界3△一3的外平面图,即我们证明了 △ ≥ 3且不含几个特定结构的外平面图G满足X’s（C）≤3△-4.在第四章中,我们研究了弦图的强边染色,证明了对每个弦图G都有χ’s（G）≤△2-2△+3,这说明强边染色猜想对这类图成立.在第五章中,我们研究了若干图的星边染色,尤其是给出了平面图以及一些特殊平面图的星边色数的较好上界,并证明了以下结果:（1）若G是一个平面图,则有χ’st（G）≤ 2.75△+18.（2）若G是一个无K4-子式的图,则有χ;st（G）≤ 2.25△+6.（3）若G是不含4-圈的平面图,则有χ’st（G）≤[1.5△]+18.（4）若G是围长g（G）≥ 5的平面图,则有χ’st（G）≤[1.5△]+13.（5）若G是围长g（G）≥ 8的平面图,则有χ’st（G）≤[1.5△]+3.（6）若G是一个外平面图,则有χ’st（G）≤[1.5△]+5.在第六章中,我们研究了最大度是4的一般图的星边染色,证明了以下两个结果:（1）若G是△=4的图,则有χ’st（G）≤ 14.（2）若G是△=4的二部图,则有χ’st（G）≤ 13.

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 基本概念与符号
•     1.1.1 图的定义
•     1.1.2 平面图
•   1.2 强边染色和星边染色的研究概况
•     1.2.1 文中涉及的染色问题
•     1.2.2 强边染色的研究进展
•     1.2.3 星边染色的研究进展
•   1.3 本文的主要结果
• 第二章 最大度为4的平面图的强边染色
•   2.1 预备知识
•   2.2 极小反例的结构性质
•   2.3 主要结果及证明
• 第三章 外平面图的强边染色
•   3.1 预备知识
•   3.2 主要结果及证明
•     3.2.1 ? ≥ 4 的外平面图
•     3.2.2 ? = 3 的外平面图
• 第四章 弦图的强边染色
•   4.1 弦图的结构性质
•   4.2 主要结果及证明
• 第五章 若干图的星边染色
•   5.1 边分解
•     5.1.1 平面图的边分解
• 4-子式的图的边分解'>    5.1.2 无K₄-子式的图的边分解
•     5.1.3 外平面图的边分解
•   5.2 一个关键的不等式
•   5.3 星边色数
•     5.3.1 平面图的星边色数
• 4-子式的图的星边色数'>    5.3.2 无K₄-子式的图的星边色数
•     5.3.3 外平面图的星边色数
• 第六章 最大度为4的图的星边染色
•   6.1 预备知识
•   6.2 ? = 4 的图
•   6.3 ? = 4 的二部图
•   6.4 关于下界的讨论
• 参考文献
• 攻读学位期间取得的研究成果
• 致谢

文章来源

类型: 博士论文

作者: 王莹

导师: 王维凡

关键词: 强边染色,星边染色,平面图,外平面图,权转移,边分解

来源: 浙江师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江师范大学

分类号: O157.5

DOI: 10.27464/d.cnki.gzsfu.2019.000005

总页数: 105

文件大小: 1808K

下载量: 45