论文部分内容阅读
本文研究有限简单图.图G的一个injecdve k-染色是指映射φ:V(G)→{1,2,….,k},使得G中有公共邻点的两个顶点u,v满足φ(u)≠φ(v).如果图G有一个injectivek-染色,则称图G是injectivek-可染的.使得图G有一个injectivek-染色的最小k值称为G的injective色数,记作xi(G).用xli(G)表示图G的injective列表色数. 图的injective染色是南Hahn等人在2002年基于复杂理论的研究提出的.他们研究了超立方体的injective色数,并将其运用到编码纠错理论中.Injective染色与图的L(0,1)-标号以及平方图染色有着密切联系.2010年,Lu(z)ar提出了关于平面图的一个猜想:设G是平面图,若△=3,则xi(G)≤5;若4≤△≤7,则xi(G)≤△+5;若△≥8,则xi(G)≤([)3△/2」+1.猜想的上界能够达到. 本论文分为四章,主要研究了在不含短圈条件下的平面图的injective染色,所得结论改进了现有的一些结果,同时肯定了上述部分猜想.第一章介绍了本论文所涉及的有关定义,并对injective染色的研究现状和存在的问题做了一个综述.第二章主要讨论围长至少为5的平面图的injective列表染色.第三章分别讨论了xli(G)≤△+1和xli(G)=△的充分条件.第四章给出一个不含3-,4-,8-圈平面图的injective列表色数的较小上界.