若干图类的邻强边染色与2-强边染色问题研究

论文摘要

具有重要的理论意义和实际意义的各种染色问题,一直是图论中的热点话题之一。离散系统中的许多问题都可以转化为图着色问题,例如,给定图G,不包含子图的G的n个顶点的图的边的最大数目就依赖于图G的色数。因此Jensen和Toft断言:图着色理论在离散数学中处于中心的地位。在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规则进行分类的问题,例如时间表问题、排序问题、排课表问题、存储问题、电路安排、任务分配等等,都与图着色理论密切相关。所谓图着色是指对图中的顶点、边（对平面图而言还有面）等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色。随着染色理论的发展又出现了许多新的染色,例如:全着色、列表着色、点强全着色、强边着色、强着色、关联着色、圈着色、距离面着色、区间着色、r-强边着色、完备着色及动态着色等,这些染色已成为现在图着色领域中新的热点.对于过去很多未解决的问题我们可以把它转化为一个新的染色问题,使原问题变得简单易懂并且便于研究。本文主要研究的是图的邻强边染色与2-强边染色问题。首先借助于Akbari对树2-强边染色及3-强边染色的研究与张忠辅对树邻强边染色的研究,给出了对树进行2-强边染色时,2-强边色数等于最大度加1的充分条件是具有最大度的两个顶点的距离小于等于2。然后根据圈、完全图、完全二部图、轮图、项链、Pn2、Pn3、Pn4、Pn5、单圈图、若干联图、方形网格与六角网络的结构特点及其具有最大度的顶点之间的关系,研究了它们的2-强边染色问题,确定了它们的2-强边色数与最大度的关系,并且给出了它们的2-强边染色方案。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 邻强边染色与2-强边染色问题的发展及现状
• 1.3 本文的研究内容与安排
• 第2章 基本概念与预备知识
• 2.1 基本概念与记号
• 2.2 邻强边染色与2-强边染色的主要结论
• 第3章 一般图的邻强边染色与2-强边染色
• 3.1 树的2-强边染色
• 3.2 圈的2-强边染色
• 3.3 完全图的2-强边染色
• 3.4 完全二部图的2-强边染色
• 3.5 轮图的2-强边染色
• 3.6 项链的2-强边染色
• n^k的2-强边染色'>3.7 P_n^k的2-强边染色
• n²的2-强边染色'>3.7.1 P_n²的2-强边染色
• n³的2-强边染色'>3.7.2 P_n³的2-强边染色
• n⁴（n≥15）的2-强边染色'>3.7.3 P_n⁴（n≥15）的2-强边染色
• n⁵（n≥23）的2-强边染色'>3.7.4 P_n⁵（n≥23）的2-强边染色
• 3.8 单圈图的邻强边染色与2-强边染色
• 第4章 若干联图的2-强边染色
• m∨P_n的2-强边染色'>4.1 O_m∨P_n的2-强边染色
• m∨P_n的2-强边染色'>4.2 P_m∨P_n的2-强边染色
• m∨C_n的2-强边染色'>4.3 P_m∨C_n的2-强边染色
• m∨P_n的2-强边染色'>4.4 S_m∨P_n的2-强边染色
• 第5章 平面网格的2-强边染色
• 5.1 平面网格的坐标系
• 5.1.1 方形网格的坐标系
• 5.1.2 六角网格的坐标系
• 5.2 网格的2-强边染色
• 5.2.1 方形网格的2-强边染色
• 5.2.2 六角网格的2-强边染色
• 第6章 结束语
• 6.1 本文研究的主要工作
• 6.2 待研究的问题
• 参考文献
• 攻读学位期间公开发表论文
• 致谢
• 研究生履历