图的限制染色及其相关问题的研究

论文题目: 图的限制染色及其相关问题的研究

论文类型: 博士论文

论文专业: 基础数学

作者: 赵永强

导师: 何文杰

关键词: 限制染色,染色,色数,跨度,边跨度,列表分配,列表染色,列表染色,唯一列表染色,唯一列表染色,唯一列表可染图,列表非正常染色,性质,完全多部图,欧拉公式,角色分配,角色分配,限制大小的角色分配,阈角色分配,阈近角色分配,竞争图,步竞争图,竞争数,步竞争数,进化图,进化数,进化有向图

文献来源: 河北师范大学

发表年度: 2005

论文摘要: 图的染色是经典的图论问题,图的染色理论在离散数学中占有很重要的地位,并且有着丰富的理论结果和广泛的实际应用。近年来大量的研究结果涌现在图的限制染色领域。在本文,我们研究几个有关图的限制染色的问题。 图的T-染色提供了研究频道分配问题的一个模型。Tesman[116]和Liu[74,75]研究了满足一定条件的T-集。本文用类似的方法推广了他们的一些结果。另外,Cozzens and Roberts[22]提出了,对于T={0,1,2…,k-1}时,计算非完全图的T-边跨度的问题。Liu[73]对于奇圈研究了这个问题。Hu,Juan and Chang[51]对于d阶n-圈,Cnd,研究了这个问题。在本文,我们继续研究图Cnd的边跨度,得到了一些更好的结果。 图的列表染色概念是图的普通染色概念的一个推广。Ghebleh and Mahmoodian[36]广泛地研究了完全多部图的唯一列表可染性,特别是唯一3-列表可染性。他们几乎完全刻画了唯一3-列表可染完全多部图。在本文,我们证明了图K2,3,4不是唯一3-列表可染的,从而完全刻画了唯一3-列表可染完全多部图。另外,Lih et al.[72]在研究平面图的列表非正常染色时,结合 欧拉公式用放电的方法证明了每个不含4-圈和i-圈的平面图是（3,1）*-可选的,其中i∈{5,6,7}。本文指出,对于2-连通图,只用欧拉公式和图的结构性质就能证明这些以及其它的一些结果。 图的角色分配,或者说角色染色,是研究社会角色的一个图论模型。在本文,我们研究图的k-角色分配以及它的一些变形。对k-角色可分配图、限制k-角色可分配图和阈近k-角色可分配图分别给出了一些充分或充要条件。另外我们还研究了在几种图运算下的k-角色

论文目录:

摘要

ABSTRACT

插图目录

第一章 引言

§1.1 综述

§1.2 基本概念

第二章 T-染色

§2.1 T-染色的T-集

§2.1.1 预备知识

§2.1.2 主要结果

§2.2 图C_n~d的T-边跨度

§2.2.1 esPT(C_n~d)的上界

§2.2.2 esPT(C_n~d)的下界

§2.2.3 结论

第三章 列表染色

§3.1 唯一3-列表可染的完全多部图

§3.1.1 引理和命题

§3.1.2 主要结果

§3.1.3 结论

§3.2 欧拉公式在(3，1)~*-列表染色中的应用

§3.2.1 引理

§3.2.2 主要结果

第四章 角色分配

§4.1 图的k-角色分配

§4.1.1 k-角色可分配图

§4.1.2 限制k-角色可分配图

§4.1.3 k-阈近角色可分配图

§4.1.4 极大和极小k-角色可分配图

§4.2 一些图运算下的k-角色分配

§4.2.1 图的联

§4.2.2 图的笛卡尔积

§4.2.3 图的字典式积

§4.2.4 图的弱直积

§4.2.5 Mycielski图

第五章 竞争图和进化图

§5.1 竞争数和进化数

§5.1.1 竞争数

§5.1.2 进化数

§5.2 路的m-步竞争数

参考文献

索引

致谢

攻读博士学位期间撰写的学术论文

发布时间: 2005-08-08

相关论文

• [1].关于图染色中若干参数的研究[D]. 卜月华.上海大学2008
• [2].图的广义着色[D]. 杨爱峰.郑州大学2004
• [3].图的控制数及其相关参数[D]. 单而芳.上海大学2005
• [4].图的点荫度和点线性荫度[D]. 左连翠.山东大学2005
• [5].关于图的可选择性与唯一列表可染图研究[D]. 申玉发.河北师范大学2006
• [6].图的列表着色和双圈覆盖猜想[D]. 王国平.新疆大学2006
• [7].图的边覆盖染色及分数边染色[D]. 王纪辉.山东大学2006
• [8].设计的染色及其相关问题的研究[D]. 李善海.上海交通大学2006
• [9].边染色图中的匹配、圈及图的圆染色[D]. 王光辉.山东大学2007
• [10].图的f-染色和均匀边染色[D]. 张霞.山东大学2007

标签：限制染色论文;  染色论文;  色数论文;  跨度论文;  边跨度论文;  列表分配论文;  列表染色论文;  唯一列表染色论文;  唯一列表可染图论文;  列表非正常染色论文;  性质论文;  完全多部图论文;  欧拉公式论文;  角色分配论文;  限制大小的角色分配论文;  阈角色分配论文;  阈近角色分配论文;  竞争图论文;  步竞争图论文;  竞争数论文;  步竞争数论文;  进化图论文;  进化数论文;  进化有向图论文;