摘要
2-距离染色是使得距离至多为2的顶点染不同色的一种顶点染色.1977年,Wegner猜想9种颜色可以使最大度为4的平面图有一个2-距离染色.本文证明了最大度为4的平面图用13种颜色可以使之有一个2-距离染色,而对不含三角形且最大度为4的平面图用11种颜色就可以了.
The 2-distance coloring of a graph is a coloring of its vertices such that any two vertices at distance at most two have different colors.In 1977,Wegner conjectured that 9 colors are sufficient for a planar graph with maximum degree 4 to have a 2-distance coloring.We prove that every planar graph with maximum degree 4 has a 2-distance coloring with 13 colors;additionally,we can reduce this bound to 11 if the planar graph is triangle-free.
作者
卜月华
朱旭波
朱俊蕾
BU Yuehua;ZHU Xubo;ZHU Junlei(School of Mathematical Sciences,Zhejiang Normal University,Jinhua,Zhejiang,321004,P.R.China;College of Data Science,Jiaxing University,Jiaxing,Zhejiang,314001,P.R.China)
出处
《数学进展》
CSCD
北大核心
2024年第2期281-291,共11页
Advances in Mathematics（China）
基金
Supported by NSFC(Nos.11901243,11771403)
Natural Science Foundation of Zhejiang Province(No.LQ19A010005)。
