论文部分内容阅读
本文仅考虑无向有限简单图.对于一个给定的图G，图G的顶点集，边集，最大度，最小度以及G中顶点u，v间的距离分别用V(G)，E(G)，△(G)，δ(G)和dG（u，v）来表示. 如果能将一个图G画到平面上并使它的边只在顶点处相交，那么称该图G为平面图.约定:本文所指的平面图已是一个平面嵌入.用F(G)表示平面图G的面集.对(V)x∈V(G)∪F(G)，G中x的度用dG（x）来表示，简记为d(x). 图G的k-2-距离染色是指映射ψ:V(G)→{1，2,…，k}，满足:若0＜dG(u，v)≤2，有|ψ(u）-ψ（v）|≥1.称x2(G)=min{k|G有一个k-2-距离染色}为图G的2-距离色数. 图的L(1，1)-标号是指映射φ:V(G)→{0，1，2，…，k}，满足:当dG(u，v)=1时，|φ(u)-φ(u)|≥1;当dG(u，v)=2时，|φ(u)-φ(v)|≥1.类似地，把标号数定义为λp，q(G). 图G的一个顶点列表配置L={L(v)|v∈V(G)｝是一个颜色集合簇.若G的一个正常顶点染色ψ满足ψ(v)∈L(v)，(V)v∈V(G)，则称ψ是G的一个L-染色或称G是L-可染的.若对G的任何一个配置列表L满足|L(v)|≥k((V)v∈V(G))，G都是L-可染的，则称G是k-可选的.称ch(G)=min{k|G是k-可选的}为G的顶点列表色数.类似地，用ch2(G)来表示图G的L-2-距离色数. 本论文分为四章，主要研究在不含短圈条件下的图的2-距离染色和2-距离列表染色.第一章主要介绍了本论文所涉及的相关概念，并对2-距离染色（列表染色）的研究现状和存在的问题做了一个综述.第二章主要讨论不含3，4，7-圈的平面图G是(△(G)+4)-2-距离可染的.第三章给出一个围长至少为5且不含相交5-圈的平面图的2-距离染色.第四章讨论了简单图的2-距离列表染色.