A smaller upper bound for the list injective chromatic number of planar graphs

Hongyu Chen; Li Zhang; Hongyu Chen; Li Zhang

doi:10.3934/math.2025014

AIMS Mathematics

2025, Volume 10, Issue 1: 289-310. doi: 10.3934/math.2025014

Previous Article Next Article

Research article

A smaller upper bound for the list injective chromatic number of planar graphs

Hongyu Chen ¹,
Li Zhang ^{2
,
,}

1.
School of Science, Shanghai Institute of Technology, Shanghai, 201418, China
2.
School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai, 201209, China

Received: 21 June 2024 Revised: 31 August 2024 Accepted: 08 September 2024 Published: 07 January 2025
MSC : 05C10, 05C15

An injective vertex coloring of a graph $ G $ is a coloring where no two vertices that share a common neighbor are assigned the same color. If for any list $ L $ of permissible colors with size $ k $ assigned to the vertices $ V(G) $ of a graph $ G $, there exists an injective coloring $ \varphi $ in which $ \varphi(v)\in L(v) $ for each vertex $ v\in V(G) $, then $ G $ is said to be injectively $ k $-choosable. The notation $ \chi_{i}^{l}(G) $ represents the minimum value of $ k $ such that a graph $ G $ is injectively $ k $-choosable. In this article, for any maximum degree $ \Delta $, we demonstrate that $ \chi_{i}^{l}(G)\leq\Delta+4 $ if $ G $ is a planar graph with girth $ g\geq5 $ and without intersecting 5-cycles.
- list injective coloring,
- maximum degree,
- girth,
- planar graph
Citation: Hongyu Chen, Li Zhang. A smaller upper bound for the list injective chromatic number of planar graphs[J]. AIMS Mathematics, 2025, 10(1): 289-310. doi: 10.3934/math.2025014

Related Papers:

Abstract

An injective vertex coloring of a graph $ G $ is a coloring where no two vertices that share a common neighbor are assigned the same color. If for any list $ L $ of permissible colors with size $ k $ assigned to the vertices $ V(G) $ of a graph $ G $, there exists an injective coloring $ \varphi $ in which $ \varphi(v)\in L(v) $ for each vertex $ v\in V(G) $, then $ G $ is said to be injectively $ k $-choosable. The notation $ \chi_{i}^{l}(G) $ represents the minimum value of $ k $ such that a graph $ G $ is injectively $ k $-choosable. In this article, for any maximum degree $ \Delta $, we demonstrate that $ \chi_{i}^{l}(G)\leq\Delta+4 $ if $ G $ is a planar graph with girth $ g\geq5 $ and without intersecting 5-cycles.

References

[1]	O. Borodin, A. Ivanova, List injective colorings of planar graphs, Discrete Math., 311 (2011), 154–165. https://doi.org/10.1016/j.disc.2010.10.008 doi: 10.1016/j.disc.2010.10.008
[2]	Y. Bu, C. Huang, List injective coloring of a class of planar graphs without short cycles, Discrete Math. Algorithms Appl., 10 (2018), 1850068. https://doi.org/10.1142/S1793830918500684 doi: 10.1142/S1793830918500684
[3]	Y. Bu, K. Lu, Injective coloring of planar graphs with girth 7, Discrete Math. Algorithms Appl., 4 (2012), 1250034. https://doi.org/10.1142/S1793830912500346 doi: 10.1142/S1793830912500346
[4]	Y. Bu, K. Lu, List injective coloring of planar graphs with girth 5, 6, 8, Discrete Appl. Math., 161 (2013), 1367–1377. https://doi.org/10.1016/j.dam.2012.12.017 doi: 10.1016/j.dam.2012.12.017
[5]	Y. Bu, C. Wang, S. Yang, List injective coloring of planar graphs, Ars Combin., 141 (2018), 191–211.
[6]	Y. Bu, S. Yang, List injective coloring of planar graphs with girth $g\geq5$, Discrete Math. Algorithms Appl., 6 (2014), 1450006. https://doi.org/10.1142/S1793830914500062 doi: 10.1142/S1793830914500062
[7]	Y. Bu, P. Ye, Injective coloring of planar graphs with girth 5, Front. Math. China, 17 (2022), 473–484. https://doi.org/10.1007/s11464-022-1018-x doi: 10.1007/s11464-022-1018-x
[8]	H. Chen, J. Wu, List injective coloring of planar graphs with girth $g\geq6$, Discrete Math., 339 (2016), 3043–3051. https://doi.org/10.1016/j.disc.2016.06.017
[9]	W. Dong, W. Lin, Injective coloring of planar graphs with girth 6, Discrete Math., 313 (2013), 1302–1311. https://doi.org/10.1016/j.disc.2013.02.014 doi: 10.1016/j.disc.2013.02.014
[10]	W. Dong, W. Lin, Injective coloring of planar graphs with girth 5, Discrete Math., 315 (2014), 120–127. https://doi.org/10.1016/j.disc.2013.10.017 doi: 10.1016/j.disc.2013.10.017
[11]	G. Hahn, J. Kratochvíl, J. Sirá, D. Sotteau, On the injective chromatic number of graphs, Discrete Math., 256 (2002), 179–192. https://doi.org/10.1016/S0012-365X(01)00466-6 doi: 10.1016/S0012-365X(01)00466-6
[12]	C. Huang, Injective coloring of planar graphs on the condition of girth at least 5, East China Normal University, 2016.
[13]	B. Lužar, Planar graphs with largest injective chromatic numbers, IMFM Preprint Series, 2010.
[14]	B. Lužar, R. Škrekovski, Counterexamples to a conjecture on injective colorings, Ars Math. Contemp., 8 (2015), 291–295.

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)