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 条
[11]  
Borodin OV(2014)Injective coloring of sparse graphs Discrete Math. 315–316 120-127
[12]  
Glebov AN(2016)Injective coloring of graphs with low average degree J. Comb. Optim. 32 645-655
[13]  
Ivanova AO(2017)Injective coloring of planar graphs with girth 6 Discrete Appl. Math. 217 495-505
[14]  
Neustroeva TK(2010)Injective coloring of plane graphs with girth 5 Discrete Math. 310 585-590
[15]  
Tashkinov VA(2008)An improved bound on 2-distance coloring plane graph with girth 5 Eur J Comb 29 838-849
[16]  
Bu Y(2012)On 2-distance coloring of plane graphs with girth 5 Discrete Math 256 179-192
[17]  
Zhu X(2009)Some bounds on the injective chromatic number of graphs Discrete Math 309 5636-5649
[18]  
Cranston D(2005)Coloring squares of planar graphs with girth six J Comb Theory Ser B 94 189-213
[19]  
Kim S(2003)On the injective chromatic number of graphs J Graph Theory 42 110-124
[20]  
Yu G(2003)Injective colorings of planar graphs with few colors SIAM J Discrete Math 17 264-275
123456