On the list injective coloring of planar graphs without a $ {4^ - } $-cycle intersecting with a $ {5^ - } $-cycle

Yuehua Bu; Hongrui Zheng; Hongguo Zhu; Yuehua Bu; Hongrui Zheng; Hongguo Zhu

doi:10.3934/math.2025083

AIMS Mathematics

2025, Volume 10, Issue 1: 1814-1825. doi: 10.3934/math.2025083

Previous Article Next Article

Research article Special Issues

On the list injective coloring of planar graphs without a $ {4^ - } $-cycle intersecting with a $ {5^ - } $-cycle

1.
Department of Mathematics, Zhejiang Normal University, Zhejiang, China
2.
Department of Basics, Zhejiang Guangsha Vocational and Technical University of Construction, Zhejiang, China

Received: 11 November 2024 Revised: 28 December 2024 Accepted: 17 January 2025 Published: 24 January 2025
MSC : 05C10, 05C15

An injective coloring of a graph $ G $ is a vertex coloring such that a pair of vertices obtain distinct colors if there is a path of length two between them. It is proved in this paper that $ \chi _i^l(G) \le \Delta + 4 $ if $ \Delta \ge 12 $ when $ G $ does not have a $ {4^ - } $-cycle intersecting with a $ {5^ - } $-cycle. Our result improves a previous result of Cai et al. in 2023, who showed that $ \chi _i^l(G) \le \Delta + 4 $ when $ \Delta \ge 12 $ and $ G $ has disjoint $ {5^ - } $-cycles.
- injective coloring,
- face,
- discharging method,
- planar graph,
- cycle
Citation: Yuehua Bu, Hongrui Zheng, Hongguo Zhu. On the list injective coloring of planar graphs without a $ {4^ - } $-cycle intersecting with a $ {5^ - } $-cycle[J]. AIMS Mathematics, 2025, 10(1): 1814-1825. doi: 10.3934/math.2025083

Related Papers:

Abstract

An injective coloring of a graph $ G $ is a vertex coloring such that a pair of vertices obtain distinct colors if there is a path of length two between them. It is proved in this paper that $ \chi _i^l(G) \le \Delta + 4 $ if $ \Delta \ge 12 $ when $ G $ does not have a $ {4^ - } $-cycle intersecting with a $ {5^ - } $-cycle. Our result improves a previous result of Cai et al. in 2023, who showed that $ \chi _i^l(G) \le \Delta + 4 $ when $ \Delta \ge 12 $ and $ G $ has disjoint $ {5^ - } $-cycles.

References

[1]	O. V. Borodin, A. O. Ivanova, List injective coloring 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), 663–672. https://doi.org/10.1142/S1793830918500684 doi: 10.1142/S1793830918500684
[3]	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
[4]	J. Cai, W. Li, W. Cai, M. Dehmer, List injective coloring of planar graphs, Appl. Math. Comput., 439 (2023), 127631. https://doi.org/10.1016/j.amc.2022.127631 doi: 10.1016/j.amc.2022.127631
[5]	H. Chen, List injective coloring of planar graphs with girth at least five, Bull. Korean Math. Soc., 61 (2024), 263–271. https://doi.org/10.4134/BKMS.b230097 doi: 10.4134/BKMS.b230097
[6]	H. Chen, J. Wu, List injective coloring of planar graphs with girth g$\ge$6, Discrete Math., 339 (2016), 3043–3051. https://doi.org/10.1016/j.disc.2016.06.017 doi: 10.1016/j.disc.2016.06.017
[7]	M. Chen, G. Hahn, A. Raspaud, W. Wang, Some results on the injective chromatic number of graphs, J. Comb. Optim., 24 (2012), 299–318. https://doi.org/10.1007/s10878-011-9386-2 doi: 10.1007/s10878-011-9386-2
[8]	Q. Fang, L. Zhang, Sharp upper bound of injective coloring of planar graphs with girth at least 5, J. Comb. Optim., 44 (2022), 1161–1198. https://doi.org/10.1007/s10878-022-00880-z doi: 10.1007/s10878-022-00880-z
[9]	G. Hahn, J. Kratochvíl, J. Širáň, 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
[10]	S. J. Kim, X. Lian, The square of every subcubic planar graph of girth at least 6 is 7-choosable, Discrete Math., 347 (2024), 113963. https://doi.org/10.1016/j.disc.2024.113963 doi: 10.1016/j.disc.2024.113963
[11]	W. Li, J. Cai, G. Yan, List injective coloring of planar graphs, Acta Math. Appl. Sin. Engl. Ser., 38 (2022), 614–626. https://doi.org/10.1007/s10255-022-1103-7 doi: 10.1007/s10255-022-1103-7
[12]	B. Lužar, Planar graphs with largest injective chromatic number, IMFM Preprint series, 48 (2010), 1–6.
[13]	B. Lužar, R. Škrekovski, Counterexamples to a conjecture on injective colorings, Ars Math. Contemp., 8 (2015), 291–295. https://doi.org/10.26493/1855-3974.516.ada doi: 10.26493/1855-3974.516.ada
[14]	B. Lužar, R. Škrekovski, M. Tancer, Injective coloring of planar graphs with few colors, Discrete Math., 309 (2009), 5636–5649. https://doi.org/10.1016/j.disc.2008.04.005 doi: 10.1016/j.disc.2008.04.005
[15]	G. Wegner, Graphs with given diameter and a coloring problem, Germany: University of Dortmund, 1977.
[16]	J. Yu, M. Chen, W. Wang, 2-Distance choosability of planar graphs with a restriction for maximum degree, Appl. Math. Comput., 448 (2023), 127949. https://doi.org/10.1016/j.amc.2023.127949 doi: 10.1016/j.amc.2023.127949

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)