平面图的DP-3-染色

发布时间：2023-04-22 11:33

　　点染色是指颜色集对图G中各个顶点的一种分配,使得任意两个相邻的顶点被染上不同的颜色.随着四色定理的产生与发展,人们定义了多种多样的非正常染色方法,如列表染色.近来,Dvorak和Postle又介绍了一种新的染色方法——DP-染色,它可以看作是列表染色的一种推广.DP-染色的实质是将每个点变为团数为颜色列表数的团,再对相邻的点进行任意匹配,最后找出其中的独立集.虽然不是所有的列表染色都能推广到DP-染色,例如偶圈,但DP-染色仍然是一种有效的研究方法.事实上已经有很多列表染色的结论被推广到DP-染色上了,其中较为著名的有:不含3-圈,4-圈的平面图是DP-3-可染的.人们对于DP-3-可染的平面图的充分条件十分感兴趣.本文则主要证明了以下两个定理:(1)不含4-,6-圈,且不含相邻5-圈,三角形距离dΔ≥ 3的平面图是DP-3-可染的.(2)不含5-,6-圈,且4-圈距离d□≥3,三角形距离dΔ≥ 3的平面图是DP-3-可染的.本文研究方法为首先假设存在满足定理条件的最小反例,研究最小反例的结构特点,然后对其点和面进行赋权,再制定权转移规则,通过权转移过程和的不变性得到矛盾,从而说明这样...

【文章页数】：28 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 序论
第二章 可约结构
第三章 定理1.4的证明
    3.1 最小反例的结构特点
    3.2 权转移过程
第四章 定理1.5的证明
    4.1 最小反例的结构特点
    4.2 权转移过程
第五章 研究展望
参考文献
致谢



本文编号：3797560