Injective coloring of planar graphs with girth 5

Yuehua Bu; Qiang Yang; Junlei Zhu; Hongguo Zhu; Yuehua Bu; Qiang Yang; Junlei Zhu; Hongguo Zhu

doi:10.3934/math.2023872

AIMS Mathematics

2023, Volume 8, Issue 7: 17081-17090. doi: 10.3934/math.2023872

Previous Article Next Article

Research article

Injective coloring of planar graphs with girth 5

1.
Department of Mathematics Sciences, Zhejiang Normal University, Zhejiang, 321004, China
2.
Department of Basics, Zhejiang Guangsha Vocational and Technical University of Construction, Zhejiang, 322100, China
3.
College of Data Science, Jiaxing University, Zhejiang, 314001, China

Received: 23 February 2023 Revised: 20 April 2023 Accepted: 24 April 2023 Published: 17 May 2023
MSC : 05C10, 05C15

A $ k $-injective-coloring of a graph $ G $ is a mapping $ c: \; V\left(G \right) \to \left\{ {1, 2, \cdots, k} \right\} $ such that $ c\left(u \right) \ne c\left(v \right) $ for any two vertices $ u $ and $ v $ if $ u $ and $ v $ have a common vertex. The injective chromatic number of $ G $, denoted by $ {\chi _i}\left(G \right) $, is the least $ k $ such that $ G $ has an injective k-coloring. In this paper, we prove that for planar graph $ G $ with $ g\left(G \right) \ge 5 $, $ \Delta \left(G \right) \ge 20 $ and without adjacent 5-cycles, $ {\chi _i}\left(G \right) \le \Delta \left(G \right) + 2 $.
- injective coloring,
- planar graph,
- cycle
Citation: Yuehua Bu, Qiang Yang, Junlei Zhu, Hongguo Zhu. Injective coloring of planar graphs with girth 5[J]. AIMS Mathematics, 2023, 8(7): 17081-17090. doi: 10.3934/math.2023872

Related Papers:

Abstract

A $ k $-injective-coloring of a graph $ G $ is a mapping $ c: \; V\left(G \right) \to \left\{ {1, 2, \cdots, k} \right\} $ such that $ c\left(u \right) \ne c\left(v \right) $ for any two vertices $ u $ and $ v $ if $ u $ and $ v $ have a common vertex. The injective chromatic number of $ G $, denoted by $ {\chi _i}\left(G \right) $, is the least $ k $ such that $ G $ has an injective k-coloring. In this paper, we prove that for planar graph $ G $ with $ g\left(G \right) \ge 5 $, $ \Delta \left(G \right) \ge 20 $ and without adjacent 5-cycles, $ {\chi _i}\left(G \right) \le \Delta \left(G \right) + 2 $.

References

[1]	G. Hahn, J. Kratochvíl, J. $\check{S}$ir$\acute{a}\check{n}$, 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
[2]	Y. Bu, C. Qi, J. Zhu, T. Xu, Injective coloring of planar graphs, Theoret. Comput. Sci., 857 (2021), 114–122. https://doi.org/10.1016/j.tcs.2021.01.007 doi: 10.1016/j.tcs.2021.01.007
[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]	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
[5]	B. Lu$\breve{z}$ar, R. $\breve{S}$krekovski, M. Tancer, Injective colorings 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
[6]	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
[7]	Y. Bu, P. Ye, Upper bounds for the injective coloring of planar graphs with girth at least five, Adv. Math., 47 (2018), 363–372.
[8]	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
[9]	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

Reader Comments

Your name:*

Email:*
© 2023 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)