2-Distance coloring of planar graphs with girth 5

被引:0
作者
Wei Dong
Baogang Xu
机构
[1] Nanjing XiaoZhuang University,School of Information and Engineering
[2] Nanjing Normal University,Institute of Mathematics, School of Mathematical Sciences
来源
Journal of Combinatorial Optimization | 2017年 / 34卷
关键词
Girth; Planar graph; 2-Distance coloring; 05C15; 05C78;
D O I
暂无
中图分类号
学科分类号
摘要
A vertex coloring is said to be 2-distance if any two distinct vertices of distance at most 2 receive different colors. Let G be a planar graph with girth at least 5. In this paper, we prove that G admits a 2-distance coloring with at most Δ(G)+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta (G)+3$$\end{document} colors if Δ(G)≥339\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta (G)\ge 339$$\end{document}.
引用
收藏
页码:1302 / 1322
页数:20
相关论文
共 51 条
[1]  
Borodin OV(2013)Colorings of plane graphs: a survey Discrete Math. 313 517-539
[2]  
Borodin OV(2009)2-Distance Discrete Math. 309 6496-6502
[3]  
Ivanova AO(2011)-coloring of planar graphs with girth six and Sibirsk. Mat. Zh. 52 30-38
[4]  
Borodin OV(2011)Injective ( Discrte Math. 311 154-165
[5]  
Ivanova AO(2004))-coloring of planar graphs with girth six Sib. Èlektron. Mat. Izv. 1 76-90
[6]  
Borodin OV(2004)List injective colorings of planar graphs Sib. Èlektron. Mat. Izv. 1 129-141
[7]  
Ivanova AO(2012)2-Distance coloring of sparse plane graphs J. Comb. Optim. 24 580-592
[8]  
Borodin OV(2010)Sufficient conditions for the 2-distance Discrete Math. 310 2965-2973
[9]  
Ivanova AO(2011)-colorability of plane graphs Algorithmica 60 553-568
[10]  
Neustroeva TK(2013)An optimal square coloring of planar graphs Discrete Math. 313 1302-1311