论文部分内容阅读
给定一个图G，用V(G)，E(G)，△(G)，δ(G)，g(G)，mad(G)和d(u，v)分别表示图G的顶点集，边集，最大度，最小度，围长，最大平均度和顶点u，v之间的距离，图G的k-2-距离染色是指一个映射(ψ):V(G)→{1，2，…，k}，使得0＜dG(u，v)≤2的顶点对u，v，有(ψ)（u）≠(ψ)(v).若图G有一个k-2-距离染色，则称图G是k-2-距离可染的，图G的2-距离色数是指使得G是k-2-距离可染的最小的正整数k，记之为X2(G).图G的一个列表配置L是指给G的每个顶点v∈V(G)分配一个可用色集合L(v).设L是G的一个列表配置，若G的一个2-距离染色(ψ)对任意的v∈V(G)满足(ψ)(v)∈L(v)，则称(ψ)是G的一个L2-距离染色.若对G的任意一个满足|L(v)|≥k的列表配置L，G都有一个L-2-距离染色，则称G是k-2-距离可选的，图G的2-距离列表色数Xl2(G)=min{k|G是k-2-距离可选的}. 关于图的2-距离染色问题，最早由Wgener于1977年提出.Wegner提出如下的一个猜想:对于平面图G，(1)若△=3，则X2(G)≤7;(2)若4≤△≤7，则X2(G)≤△+5;(3)若△≥8，则X2(G)≤[3/2△]+1.同时Wegner提出若猜想正确，那么它的上界是紧的，到目前为止，Wegner猜想仍有待研究.对于任意图，我们可以找到2-距离色数无穷大的图.1993年，Ramanathan证明了确立平面图的2-距离色数是一个N P-问题.因此，给出平面图的2-距离色数的上界受到图论学者的广泛关注. 本学位论文主要研究了最大度为5的简单图和平面图的2-距离（列表）染色问题，共分三章， 在第一章中，我们介绍了基本概念和相关领域的研究现状，并且呈现了本文的主要结果. 在第二章中，我们研究了最大度为5的简单图的2-距离列表染色，证明了下面三个结果: (1)若G是△(G)=5且mad(G)＜20/7的简单图，则Xl2(G)≤10. (2)若G是△(G)=5且mad(G)＜19/6的简单图,则Xl2(G)≤11 (3)若G是△(G)=5且mad(G)＜41/12的简单图，则Xl2(G)≤13. 在第三章中，我们研究了平面图的2-距离染色，证明了:若G是g(G)≥5且△(G)≥44的平面图，则X2(G)≤△+4.