论文部分内容阅读
图G的κ-边染色就是从边集合E(G)到颜色集合{1,2,…,κ}的一个映射,使得相邻的边得到不同的颜色.图G的边色数χ’(G)就是最小的κ,使得图G有一个正常k-边染色.图G的κ-全染色就是从点边集合V(G)u E(G)到颜色集合{1,2,…,κ}的一个映射,使得相邻的边得到不同的颜色,相邻的点得到不同的颜色,关联的点和边得到不同的颜色.图G的全色数χ’(G)就是最小的κ,使得图G有一个κ-全染色.本文研究了若干图的边染色和全染色问题,包括广义Mycielski图、3-正则图、1-平面图、平面图和奇图,主要围绕平面图边染色猜想,列表边染色猜想,全染色猜想和唯一最大度点全染色猜想,力求能给这些猜想提供更有力的证据.本学位论文共分三章.在第一章中,我们首先给出本文所需要的基本概念,然后介绍若干图的边染色和全染色的研究现状,最后呈现本文的主要结果.在第二章中,我们研究若干图的边染色.(1)刻画了广义Mycielski图的边色数;(2)考虑平面图的分数边色数,并且证明了3-正则图是(7,2)-边可染的,推进了Fulkerson猜想和Mohar猜想;(3)研究最大度点导出子图条件下的1-平面图和平面图的边染色和列表边染色问题.在第三章中,我们研究若干图的全染色.(1)证明了广义Mycielski图满足全染色猜想,并且给出类型1的若干充分条件；(2)研究最大度点导出子图条件下的1-平面图和平面图的全染色和列表全染色问题；(3)证明了奇图K(2κ+1,κ)满足全染色猜想.