论文部分内容阅读
图的染色理论是图论研究的重要问题之一有着相当广泛的应用背景.本博士论文主要研究了图的边染色问题.
设(x)(G),(a)(G),(a)list(G),(x)a(G),(x)a(G),△和g(G)分别表示一个图G的边色数、无圈边色数、无圈边列表色数、邻点可区别边色数、邻点可区别全色数、最大度和围长.
本文共分六章.第一章主要介绍了文中所用的概念和记号,概述了平面图的边染色、图的无圈边染色、图的邻点可区别边染色和全染色的最新研究进展.
第二章研究了最大度为6的可平面图是第一类的充分条件.证明了:
定理2.1.1如果G是一个不含弦-6-圈的△=6的平面图,则(x)(G)=6.定理2.2.1如果G是一个△=6的非负图并且G中不存在这样的顶点υ∈V(G)使得υ同时包含在圈长为3到6的圈中,那么(x)(G)=6.
第三章主要证明了对于不含有4-圈或不含有5-圈的平面图G,均有(a)(G)≤△+2,另外,研究了△≥5的外平面图的无圈边列表染色数.
定理3.1.1若G是一个不含5-圈的平面图,则(a)(G)≤△+2.
定理3.2.1若G是一个△≠4且不含4-圈的平面图,则(a)(G)≤△+2.
定理3.3.1若G是一个△≥5的外平面图,则(a)list(G)=△.
第四章,我们研究了最大平均度分别为5-2,7-3,3的图的邻点可区别边染色数和当△≥5时没有K4-图子式的图的邻点可区别边染色数.
推论4.1.1设G是平面图,若g(G)≥10且△≥5,则(x)a(G)=△+1当且仅当G有相邻的最大度点.
推论4.2.1若G是一个△≥5且没有K4-图子式的正常图,则△≤(x)a(G)≤△+1;且(x)a(G)=△+1当且仅当G含有相邻的最大度点.
第五章研究了最大平均度分别为8-3,3的图的邻点可区别全染色数.证明了:
推论5.1设G是平面图,若g(G)≥10且△≥5,则(x)a(G)△+1当且仅当G有相邻的最大度点.
第六章是总结以及未来工作打算.