2-Distance coloring of planar graphs without adjacent 5-cycles

被引:0
作者
Yuehua Bu
Zewei Zhang
Hongguo Zhu
机构
[1] Zhejiang Normal University,Department of Mathematics
[2] Zhejiang Guangsha Vocational and Technical University of Construction,Department of Basics
来源
Journal of Combinatorial Optimization | 2023年 / 45卷
关键词
2-Distance coloring; Planar graph; Girth; Cycle; 05C10; 05C15;
D O I
暂无
中图分类号
学科分类号
摘要
The k-2-distance coloring of graph G is a mapping c:V(G)→{1,2,…,k}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c:V(G)\rightarrow \{1,2,\ldots ,k\}$$\end{document} such that any two vertices at distance at most two from each other get different colors. The 2-distance chromatic number is the smallest integer k such that G has a k-2-distance coloring, denoted by χ2(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi _{2}(G)$$\end{document}. In this paper, we prove that every planar graph G without adjacent 5-cycles and g(G)≥5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g(G)\ge 5$$\end{document} and Δ(G)≥17\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 17$$\end{document} has χ2(G)≤Δ+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi _{2}(G)\le \Delta +3$$\end{document}.
引用
收藏
相关论文
共 17 条
  • [1] Bonamy M(2014)Graphs with maximum degree Discret Math. 317 19-32
  • [2] Lévêque B(2019) and maximum average degree less than 3 are list 2-distance J Comb Theory Ser B 134 218-238
  • [3] Pinlou A(2017)-colorable J Comb Optim 34 1302-1322
  • [4] Bonamy M(2011)Planar graphs of girth at least five are square ( J Appl Ind Math 5 221-230
  • [5] Cranston DW(2022))-choosable Acta Math Appl Sin Engl Ser 38 540-548
  • [6] Postle L(2005)2-Distance coloring of planar graphs with girth 5 J Comb Theory Ser B 94 189-213
  • [7] Dong W(2003)List 2-distance J Graph theory 42 110-124
  • [8] Xu BG(2003)-coloring of planar graphs with girth at least 7 SIAM J Discret Math 17 264-275
  • [9] Ivanova AO(undefined)List 2-distance coloring of planar graphs with girth five undefined undefined undefined-undefined
  • [10] Jin YD(undefined)A bound on the chromatic number of the square of a planar graph undefined undefined undefined-undefined