围长至少为5的平面图的injective染色*
2017-08-02卜月华叶飘飘
卜月华, 叶飘飘
(1.浙江师范大学 数理与信息工程学院,浙江 金华 321004;2.浙江师范大学 行知学院,浙江 金华 321004)
围长至少为5的平面图的injective染色*
卜月华1,2, 叶飘飘1
(1.浙江师范大学 数理与信息工程学院,浙江 金华 321004;2.浙江师范大学 行知学院,浙江 金华 321004)
通过构造一个(Δ+3)-临界图G,运用权转移的方法证明了该图G不存在.同时,用反证法证明了:对于围长至少为5的平面图G,若Δ(G)≥30,则χi(G)≤Δ+3.这个结论改进了现有的一个结果.
平面图;围长;injective染色;面
0 引 言
本文仅考虑有限简单图.对于一个平面图G,把它的顶点集、边集、面集、最大度、最小度、围长及图G中u,v间的距离分别记作V(G),E(G),F(G),Δ(G),δ(G),g(G)和dG(u,v).对于图G的一个顶点v,若d(v)=k(或d(v)≥k,或d(v)≤k),则称v为一个k-点(或k+-点,或k--点).对平面图的面也可以类似定义.∀f∈F(G),记B(f)为面f的边界迹.若u1u2…un在B(f)上按顺时针排列,则面f记为f=[u1u2…un].围长g(G)表示图G中最短圈的长度.
图G的正常顶点染色是指对图G的每个顶点分配一种颜色,使得相邻的2个顶点染不同色,其所需的最少颜色数称为图G的色数,记为χ(G).图G的injectivek-染色是指映射c:V(G)→{1,2,…,k},使得有公共邻点的2个顶点u,v满足c(u)≠c(v).若图G有一个injectivek-染色,则称图G是injectivek-可染的,并称χi(G)=min{k|G是injectivek-可染的}为图G的injective色数.
Injective染色是由Hahn等[1]提出,并且证明了对任意的平面图G都有Δ(G)≤χi(G)≤(Δ(G))2-Δ(G)+1.随后,人们对平面图的injective染色问题展开了一系列的研究.Doyon等[2]证明了:对任意围长为g(G)且最大度为Δ的平面图G,有:若g(G)≥7,则χi(G)≤Δ+3;若g(G)≥6,则χi(G)≤Δ+4;若g(G)≥5,则χi(G)≤Δ+8.文献[2-5]研究了稀疏图和平面图的injective色数的上界问题.文献[6]证明了:对于围长g(G)≥6的平面图G,χi(G)≤Δ+3;若Δ≥9,则χi(G)≤Δ+2;若Δ≥17,则χi(G)≤Δ+1.文献[7]证明了:对于围长为g(G)≥5的平面图G,χi(G)≤Δ+6;若Δ≥35,则χi(G)≤Δ+3.
问题1 是否存在一个整数M,使得g(G)≥5且Δ≥M的平面图G是injective (Δ+1)-可染的?……