完全多部图和k-细分图的唯一列表可染性

论文摘要

图的染色问题是图论的热点问题之一。其中,唯一列表染色作为染色问题的一个重要分支,引起了学者们的广泛关注。在UkLC可染图的研究中,当k=2时,所有的U2LC图已经被刻画了;当kk=3时,[U3LC完全多部图已经被完全刻画;当k=4时,研究者特征化了 6部以上的U4LC完全多部图。此外,少数特殊图类具有M（k）性质已经被证明。然而,k-细分图是UkLC的还是具有M（k）性质的,并未有研究结果出现。基于此,本文继续对UkLC完全多部图和k-细分图进行研究,并得到以下结果:首先,研究了 U5LC完全多部图的特征化问题。通过运用排列组合、分类讨论的方法,除有限个图外,特征化了至少有两部顶点数多于1的U5LC完全k（k≥9）部图。同时,证明了一系列具有M（5）性质或U5LC性质的完全k（k≤8）部图。其次,分析了完全多部图K1*r,3*（k-2）的m数。通过对图K1*（k-1）,2*（k-2）,3构造一个染色列表,证得k≥3时,K1*（k-1,）2*（k-2）,3是UkLC图。并且,讨论图K1*r,3*（k-2）的各部顶点染色情况,证明了图K1*r,3*（k-2）具有M（k）性质,从而,确定了它的m数等于kk。同时,探讨了图K1,3,3,3的唯一列表可染性,得到m（K1,3,3,3）=4。最后,完全特征化了唯一列表可染的k-细分图Gk（k≥2）。通过分析k-细分图的结构和染色情况,证明了图Gk（k≥2）具有M（3）性质且m（G1/k）≤3,同时,证得图Gk的m数等于2的充分必要条件为图G的每个块都是圈。

论文目录

摘要

Abstract

第1章绪论

1.1 图论

1.2 图的列表染色问题概述

1.3 唯一列表染色的研究现状

1.4 预备知识

1.5 本文的主要内容及结构安排

第2章唯一5-列表可染的完全多部图

2.1 相关引理

2.2 具有特殊结构的完全多部图的m数

2.3 八部以下的完全多部图的M（5）性质

2.4 九部以上的完全多部图的唯一5-列表可染性

2.5 实例

2.6 小结

1*r,3*（k-2）的m数'>第3章完全多部图K_{1*r,3*（k-2）}的m数

3.1 相关引理

1*（k-1）*（k-2）,3的唯一k-列表可染性'> 3.2 图K_{1*（k-1）*（k-2）,3}的唯一k-列表可染性

1*r,3*（k-2）的m数'> 3.3 完全多部图K_{1*r,3*（k-2）}的m数

1,3,3,3的m数'> 3.4 图K_1,3,3,3的m数

3.5 小结

第4章 k-细分图的唯一列表可染性

4.1 预备知识

1/k的M（3）性质'> 4.2 k-细分图G^1/k的M（3）性质

1/k的唯一2-列表可染性'> 4.3 k-细分图G^1/k的唯一2-列表可染性

1/2*去的唯一列表可染性'> 4.4 广义细分图G^1/2*去的唯一列表可染性

4.5 一些特殊图的k-细分图

4.6 小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

文章来源

类型: 硕士论文

作者: 张胜丹

导师: 王艳宁

关键词: 唯一列表染色,性质,完全多部图,细分图

来源: 燕山大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 燕山大学

分类号: O157.5

DOI: 10.27440/d.cnki.gysdu.2019.001496

总页数: 55

文件大小: 1944K

下载量: 7

完全多部图和k-细分图的唯一列表可染性

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢