论文部分内容阅读
本文研究的图类仅限于有限简单图.图G的一个injectivek-染色是指映射c:V(G)→{1,2,…,k},使得有公共邻点的2个顶点u,v满足c(u)≠c(v).若图G有一个injectivek-染色,则称图G是injectivek-可染的,并称xi(G)=min{k|G是injective k-可染的}为图G的injective色数.显然,图的injective染色未必是正常顶点染色.易知,图G的injective色数满足△(G)≤xi(G)≤△(G)(△(G)-1)+1,并且当G≠K2时,xi(G)≥x(G). 自Hahn等人在2002年提出了injective染色的概念后,injective染色的相关研究成为了图染色理论中重要的研究方向之一.它与图的L(0,1)-标号以及平方图染色的联系很是紧密.目前,人们主要是基于图的围长、最大度或者最大平均度等的限制条件下研究其injective色数,或者研究图的injective色数的算法复杂性. 本文探讨了不含部分短圈的平面图G的injective色数.第一部分介绍了injective染色的基本概念、述语、研究近况及存在的问题.第二部分介绍了围长至少为5的平面图,其injective色数为△+3的充分条件.第三部分介绍了injective染色的一些可研究问题.