围长至少为5的平面图的injective染色*

2017-08-02 09:32:09卜月华叶飘飘
浙江师范大学学报(自然科学版) 2017年1期
关键词:性质规则

卜月华, 叶飘飘

(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)-可染的?……

登录APP查看全文

猜你喜欢
性质规则
撑竿跳规则的制定
一类非线性随机微分方程的统计性质
数学杂志(2021年6期)2021-11-24 11:12:00
随机变量的分布列性质的应用
一类多重循环群的剩余有限性质
数独的规则和演变
完全平方数的性质及其应用
中等数学(2020年6期)2020-09-21 09:32:38
九点圆的性质和应用
中等数学(2019年6期)2019-08-30 03:41:46
规则的正确打开方式
幸福(2018年33期)2018-12-05 05:22:42
让规则不规则
Coco薇(2017年11期)2018-01-03 20:59:57
TPP反腐败规则对我国的启示