特殊图的星边染色

论文摘要

图的边染色问题具有很大的研究意义,国内外学者为确定图的边染色数问题做了大量研究工作.2008年,Liu等提出了星边染色的概念,如果图G的一个正常边染色使得G中既没有长度为4的双色路也没有长度为4的双色圈,则称这样的染色是图G的一个星边染色,使得图G有星边染色的最小颜色数称为星边染色数,记作:χ’st2（G）.以由于给定图的星边染色数与它的无圈边染色数、强边染色数有这样一个关系:图的无圈边染色数小于图的星边染色数,图的星边染色数小于图的强边染色数.因此,研究图的星边染色对于研究图的无圈边染色和强边染色是非常有意义的.本论文主要研究Halin图、k方图、广义Petersen图的星边染色问题,共分为五个部分.第一章介绍本论文的相关背景、相关概念与已有结果.阐述本论文所要用到的一些基本概念与符号,以及图的星边染色问题的相关研究结果.第二章研究有关Halin图的星边染色数问题.运用数学归纳法,通过对伴随圈的长度进行归纳,给出了 3-正则Halin图星边染色数的上界和下界:4≤χ’st（G）≤6.特别地,对于项链图Neh,假设≥ 1且为奇数,有:4≤χ’st（G）≤5.最后,通过由局部到整体的染色方式,研究了最大度△（G）≥ 6的完全Haliin图的星边染色数情况,得到:χ’st（G）≤[3Δ/2]+1.第三章研究有关k方图的星边染色数问题.通过运用边划分的方法,分别研究了图Pn2和图Pnk,k≥3的星边染色数情况.对于图Pn2,当n≥5时,其星边染色数:χ’st（Pn2）=6;对于图Pkn,≥3,给出了其星边染色数的下界和上界;对于任意圈平方图Cn2,得到:χ’st（Cn2）:≤ 9.第四章研究广义Petersen图的星边染色数问题.对于广义Petersen图P（3n,n）,n≥2,其星边染色数为:χ’st（P（3n,n））=5.第五章总结与展望.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 相关背景
•   1.2 相关概念
•   1.3 有关Halin图的定义与介绍
•   1.4 有关图的星边染色问题的已有结果
•     1.4.1 一些特殊图的星边染色数
•     1.4.2 一般图的星边染色数结果
•     1.4.3 所有点的度都小于等于3的图的星边染色数
•     1.4.4 外平面图的星边染色数
•     1.4.5 带有限制条件的平面图的星边染色数
•   1.5 本文主要方法与思想
•   1.6 本文的主要结果
• 第二章 Halin图的星边染色
•   2.1 3-正则Halin图的星边染色
•   2.2 项链图的星边染色
•   2.3 最大度大于等于6的完全Halin图的星边染色
• 第三章 k方图的星边染色
• n²的星边染色'>  3.1 P_n²的星边染色
• n^k的星边染色'>  3.2 P_n^k的星边染色
• n²的星边染色'>  3.3 C_n²的星边染色
• 第四章 广义Petersen图P（3n,n）的星边染色
•   4.1 图P（3n,n）的星边染色
•   4.2 小结
• 第五章 总结
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 侯绪玲

导师: 王涛

关键词: 星边染色,星边染色数,方图,广义图

来源: 河南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 河南大学

分类号: O157.5

总页数: 50

文件大小: 2354K

下载量: 31