论文部分内容阅读
平面图的染色一直以来都是图论研究的重要内容之一.本硕士论文研究了平面图的邻点可区别边染色.这个概念是在传统边染色基础之上,又进行了进一步的推广,在通信设计等领域有着很重要的应用,而且近几年来得到了非常广泛的研究. 设Δ(G)(简写为Δ)和g(G)分别表示图G的最大度和围长.图G的正常边染色称为邻点可区别的,如果G中任意两个相邻顶点的颜色集合不同.图G有邻点可区别边染色的最少颜色数称为邻点可区别边色数,用xa(G)表示.类似地,我们可以定义弱邻点可区别边色数,用xaΔ(G)表示. 本硕士论文共分为4章.在第1章中,我们主要介绍了本文中所用的概念和一些符号,以及概述了图的邻点可区别边染色的一些最新的研究进展. 在第2章中,我们研究了围长至少为4的平面图的邻点可区别边染色问题,确定了g(G)≥4和Δ≥6的平面图G的邻点可区别边色数. 在第3章中,我们证明了围长至少为5的平面图的邻点可区别边色数满足张忠辅教授等人提出的关于邻点可区别边色数的猜想. 在第4章中,我们研究了弱邻点可区别边染色问题.(i)证明了:设平面图G满足Δ≥9,有)xaΔ(G)≤Δ+2.(ii)证明了:设平面图G满足Δ≥13,有xaΔ(G)≤Δ+1.