论文部分内容阅读
给定一个图G,用V(G),E(G),△(G),δ(G),g(G)和d(u,v)分别表示图G的顶点集,边集,最大度,最小度,围长和顶点u,v之间的距离.图G的一个正常k-顶点染色是指一个映射f:V→{1,…,k},使得对任意uv∈E(G),满足f(u)≠f(v).若图G有一个正常k-顶点染色,那么就称图G是k-顶点可染的;使G有正常k-顶点染色的最小k值称为图G的色数,记之为x(G).对于正整数p和q,图G的一个k-L(p,q)-标号是指一个映射φ:V→{0,1,…,k},满足:(1)若uv∈E(G),|φ(u)-φ(v)|≥p;(2)若d(u,v)=2,|φ(u)-φ(v)|≥q.类似定义图G的标号数λp,q(G).特别地,当p=q=1时,图的L(1,1)-标号称为图的2-距离染色.
图的L(p,q)-标号,是从频率分配等实际问题中抽象出来的染色模型,随着其理论研究的深入和实用价值的体现,受到了众多的图论学者和理论计算机学者的关注.其中L(1,1)-标号受到了更多图论学者的关注.Wegner(1977)曾提出猜想:设G是平面图,若△(G)=3,则λ1,1(G)≤6;若4≤△(G)≤7,则λ1,1(G)≤△(G)+4;若△(G)≥8,则λ1,1(G)≤「3/2△(G)」.
本文主要围绕该猜想讨论平面图的L(1,1)-标号.第一章简述目前图的L(1,1)-标号研究现状、存在问题和陈述了本文的主要结果.第二章主要讨论围长至少为6平面图的L(1,1)-标号,部分肯定了猜想.第三章主要讨论围长至少为5的平面图的L(1,1)-标号,改进了目前的一些研究结果.第四章围绕最大度为4的平面图,给出了目前最佳的L(1,1)-标号数.