2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4

被引:0
作者
La, Hoang [1 ]
Storgel, Kenny [2 ]
机构
[1] Univ Montpellier, LIRMM, CNRS, Montpellier, France
[2] Fac Informat Studies Novo Mesto, Novo Mesto, Slovenia
关键词
Distance coloring; Injective coloring; Exact square coloring; List coloring; Planar graphs; GIRTH; CHOOSABILITY;
D O I
10.1016/j.disc.2023.113405
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In the past various distance based colorings on planar graphs were introduced. We turn our focus to three of them, namely 2-distance coloring, injective coloring, and exact square coloring. A 2-distance coloring is a proper coloring of the vertices in which no two vertices at distance 2 receive the same color, an injective coloring is a coloring of the vertices in which no two vertices with a common neighbor receive the same color, and an exact square coloring is a coloring of the vertices in which no two vertices at distance exactly 2 receive the same color. We prove that planar graphs with maximum degree A = 4 and girth at least 4 are 2-distance list (A + 7) -colorable and injectively list (A + 5) -colorable. Additionally, we prove that planar graphs with A = 4 are injectively list (A + 7) -colorable and exact square list (A + 6) -colorable.(c) 2023 Elsevier B.V. All rights reserved.
引用
收藏
页数:31
相关论文
共 42 条
[1]   List 2-facial 5-colorability of plane graphs with girth at least 12 [J].
Borodin, O. V. ;
Ivanova, A. O. .
DISCRETE MATHEMATICS, 2012, 312 (02) :306-314
[2]   List injective colorings of planar graphs [J].
Borodin, O. V. ;
Ivanova, A. O. .
DISCRETE MATHEMATICS, 2011, 311 (2-3) :154-165
[3]  
Bousquet N., arXiv
[4]   Exact Distance Colouring in Trees [J].
Bousquet, Nicolas ;
Esperet, Louis ;
Harutyunyan, Ararat ;
De Verclos, Remi De Joannis .
COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (02) :177-186
[5]   Injective choosability of subcubic planar graphs with girth 6 [J].
Brimkov, Boris ;
Edmond, Jennifer ;
Lazar, Robert ;
Lidicky, Bernard ;
Messerschmidt, Kacy ;
Walker, Shanise .
DISCRETE MATHEMATICS, 2017, 340 (10) :2538-2549
[6]   List injective coloring of a class of planar graphs without short cycles [J].
Bu, Yuehua ;
Huang, Chaoyuan .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (05)
[7]   INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH 7 [J].
Bu, Yuehua ;
Lu, Kai .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (02)
[8]   Two smaller upper bounds of list injective chromatic number [J].
Bu, Yuehua ;
Lu, Kai ;
Yang, Sheng .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (02) :373-388
[9]   List injective coloring of planar graphs with girth 5, 6, 8 [J].
Bu, Yuehua ;
Lu, Kai .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1367-1377
[10]   Injective coloring of planar graphs [J].
Bu, Yuehua ;
Chen, Dong ;
Raspaud, Andre ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672