最大度为4的平面图的2-距离染色  

2-distance Coloring for Planar Graphs with Maximum Degree 4

作　　者：卜月华[1] 朱旭波[1] 朱俊蕾 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)

机构地区：[1]浙江师范大学数学科学学院,浙江金华321004 [2]嘉兴大学数据科学学院,浙江嘉兴314001

出　　处：《数学进展》2024年第2期281-291,共11页Advances in Mathematics（China）

基　　金：Supported by NSFC(Nos.11901243,11771403);Natural Science Foundation of Zhejiang Province(No.LQ19A010005)。

摘　　要：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.

关 键 词：平面图 2-距离染色 最大度 围长 Wegner猜想 

分 类 号：O157.5[理学—数学]