论文部分内容阅读
图的染色问题是图论的一个重要分支,它起源于著名的“四色问题”.图的染色理论已广泛应用于计算机科学、无线网络等领域.设NG(v)和NG(u)表示图G的中顶点v和u的邻点所构成的集合.图G的k-邻点可区别边染色是G的一个正常k-边染色φ,使得对于任意边uv∈E(G)都有Cφ(u)≠Cφ(v),其中Cφ(v)={φ(vx)|x∈NG(v)}且Cφ(u)={φ(uy)|y ∈NG(u)}.并称使得图G有一个k-邻点可区别边染色的最小正整数k为图G的邻点可区别边色数(以下简称为NDE-色数),记为χ(G).2002年,Zhang等人首先研究了图的邻点可区别边染色,并提出了猜想:设G是阶至少为3的连通图,且G≠C5,有χa’(G)≤△(G)+2.图G的k-邻点可区别全染色是G的一个正常k-全染色ψ,使得对于任意边 vu ∈ E(G)都有Cψ(v)≠Cψ(u),其中Cψ(v)={ψ(v)}∪{ψ(vx)|x∈NG(v)}且Cψ(u)={ψ(u)}∪{ψ(uy)}|y∈NG(u)}.并称使得图G有一个k-邻点可区别全染色的最小正整数k为图G的邻点可区别全色数(以下简称为AVDT-色数),记为χa"(G).2005年,Zhang等人首先定义了图的邻点可区别全染色的概念,并且提出了猜想:设G是阶至少为2的连通图,有χa"(G)≤ Δ(G)+3.本学位论文主要研究图的NDE-色数和AVDT-色数问题,共分三章.在第一章中,介绍了本文所要用到的图论的基本概念和相关领域的研究现状,并且呈现了本文的主要结果.在第二章中,刻画了最大度△(G)≥ 14的平面图的NDE-色数.证明如下结论:若G是一个 △(G)≥ 14 的正常平面图,则 △(G)≤χa’(G)≤△(G)+1,并且χa’(G)=△(G)+l当且仅当G含有两个相邻△(G)-点.这一结果改进了 Wang和Huang对△(G)≥ 16的平面图的刻画.在第三章中,刻画了一些平面图的AVDT-色数为△(G)+1或者△(G)+2.具体来说,我们证明如下结论:(1)每一个Δ(G)=12的平面图G有χa"(G)=14当且仅当G含有两个相邻的12-点;(2)每一个△(G)=11的平面图G有χa"(G)=13当且仅当G含有两个相邻的11-点.这两个结果改进了 Wang和Huang对△(G)≥ 14的平面图的刻画和Huo等人对△(G)=13的平面图的刻画.