On star and acyclic coloring of generalized lexicographic product of graphs

Jin Cai; Shuangliang Tian; Lizhen Peng; Jin Cai; Shuangliang Tian; Lizhen Peng

doi:10.3934/math.2022786

AIMS Mathematics

2022, Volume 7, Issue 8: 14270-14281. doi: 10.3934/math.2022786

Previous Article Next Article

Research article

On star and acyclic coloring of generalized lexicographic product of graphs

1.
Department of Mathematics, Northwest for Minzu University, Gansu, Lanzhou 730030, China
2.
Key Laboratory of Streaming Data Computing Technologies and Applications, Northwest for Minzu University Lanzhou, China

Received: 05 March 2022 Revised: 11 May 2022 Accepted: 20 May 2022 Published: 31 May 2022
MSC : 05C15

A $ star \; coloring $ of a graph $ G $ is a proper vertex coloring of $ G $ such that any path of length 3 in $ G $ is not bicolored. The $ star \; chromatic \; number $ $ \chi_s(G) $ of $ G $ is the smallest integer $ k $ for which $ G $ admits a star coloring with $ k $ colors. A $ acyclic \; coloring $ of $ G $ is a proper coloring of $ G $ such that any cycle in $ G $ is not bicolored. The $ acyclic \; chromatic \; number $ of $ G $, denoted by $ a(G) $, is the minimum number of colors needed to acyclically color $ G $. In this paper, we present upper bound for the star and acyclic chromatic numbers of the generalized lexicographic product $ G[h_n] $ of graph $ G $ and disjoint graph sequence $ h_n $, where $ G $ exists a $ k- $colorful neighbor star coloring or $ k- $colorful neighbor acyclic coloring. In addition, the upper bounds are tight.
- star coloring,
- acyclic coloring,
- generalized lexicographic product,
- colorful neighbor star coloring,
- colorful neighbor acyclic coloring
Citation: Jin Cai, Shuangliang Tian, Lizhen Peng. On star and acyclic coloring of generalized lexicographic product of graphs[J]. AIMS Mathematics, 2022, 7(8): 14270-14281. doi: 10.3934/math.2022786

Related Papers:

Abstract

A $ star \; coloring $ of a graph $ G $ is a proper vertex coloring of $ G $ such that any path of length 3 in $ G $ is not bicolored. The $ star \; chromatic \; number $ $ \chi_s(G) $ of $ G $ is the smallest integer $ k $ for which $ G $ admits a star coloring with $ k $ colors. A $ acyclic \; coloring $ of $ G $ is a proper coloring of $ G $ such that any cycle in $ G $ is not bicolored. The $ acyclic \; chromatic \; number $ of $ G $, denoted by $ a(G) $, is the minimum number of colors needed to acyclically color $ G $. In this paper, we present upper bound for the star and acyclic chromatic numbers of the generalized lexicographic product $ G[h_n] $ of graph $ G $ and disjoint graph sequence $ h_n $, where $ G $ exists a $ k- $colorful neighbor star coloring or $ k- $colorful neighbor acyclic coloring. In addition, the upper bounds are tight.

References

[1]	M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen, Coloring with no $2-$colored $P_4$'s, Electron. J. Comb., 11 (2004), 1–13. https://doi.org/10.37236/1779 doi: 10.37236/1779
[2]	C. Timmons, Star coloring high girth planar graphs, Electron. J. Comb., 15 (2008), 1–17. https://doi.org/10.37236/848 doi: 10.37236/848
[3]	M. A. Shalu, T. P. Sandhya, Star coloring of graphs with girth at least five, Graph Combinator., 32 (2016), 2121–2134. https://doi.org/10.1007/s00373-016-1702-2 doi: 10.1007/s00373-016-1702-2
[4]	L. J. E. Mary, A. L. M. J. Rayen, On the star coloring of graphs formed from the cartesian product of some simple graphs, Int. J. Math. Appl., 4 (2006), 115–122.
[5]	T. Han, Z. Shao, E. Zhu, Z. Li, Star coloring of Cartesian product of paths and cycles, Ars Comb., 124 (2016), 65–84.
[6]	A. Lyons, Acyclic and star colorings of joins of graphs and an algorithm for cographs, 2009.
[7]	K. Venkatesan, V. V. Joseph, V. Mathiyazhagan, On star coloring of corona graphs, Appl. Math. E-Notes, 15 (2015), 97–104.
[8]	U. Subramanian, V. V. Joseph, On star coloring of degree splitting of comb product graphs, NIŠ Ser. Math. Inform., 35 (2020), 507–522. https://doi.org/10.22190/FUMI2002507S doi: 10.22190/FUMI2002507S
[9]	K. Kaliraj, R. Sivakami, J. Vernold Vivin, On star coloring of modular product of graphs, Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat., 69 (2020), 1235–1239. https://doi.org/10.31801/cfsuasmas.768497 doi: 10.31801/cfsuasmas.768497
[10]	V. Kowsalya, On star coloring of tensor product of graphs, Malaya J. Maternatik, 8 (2020), 2005–2007. https://doi.org/10.26637/MJM0804/0115 doi: 10.26637/MJM0804/0115
[11]	B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math., 14 (1973), 390–408. https://doi.org/10.1007/BF02764716 doi: 10.1007/BF02764716
[12]	G. Fertin, E. Godard, A. Raspaud, Minimum feedback vertex set and acyclic coloring, Inform. Process. Lett., 84 (2002), 131–139. https://doi.org/10.1016/S0020-0190(02)00265-X doi: 10.1016/S0020-0190(02)00265-X
[13]	G. Fertin, E. Godard, A. Raspaud, Acyclic and $k-$distance coloring of the grid, Inform. Process. Lett., 87 (2003), 51–58. https://doi.org/10.1016/S0020-0190(03)00232-1 doi: 10.1016/S0020-0190(03)00232-1
[14]	G. Fertin, A. Raspaud, Acyclic coloring of graphs of maximum degree $\Delta$, Discrete Math. Theor. Comput. Sci., 2005,389–396.
[15]	J. Wang, L. Miao, Acyclic coloring of graphs with maximum degree at most six, Discrete Math., 342 (2019), 3025–3033. https://doi.org/10.1016/j.disc.2019.06.012 doi: 10.1016/j.disc.2019.06.012
[16]	J. Wang, L. Miao, W. Song, Y. Liu, Acyclic coloring of graphs with maximum degree 7, Graph Combinator., 37 (2021), 455–469. https://doi.org/10.1007/s00373-020-02254-w doi: 10.1007/s00373-020-02254-w
[17]	E. Zhu, Z. Li, Z. Shao, J. Xu, C. Liu, Acyclic $3-$coloring of generalized Petersen graphs, J. Comb. Optim., 31 (2016), 902–911. https://doi.org/10.1007/s10878-014-9799-9 doi: 10.1007/s10878-014-9799-9
[18]	D. Mondal, R. I. Nishat, M. S. Rahman, S. Whitesides, Acyclic coloring with few division vertices, J. Discrete Algorithms, 23 (2013), 42–53. https://doi.org/10.1016/j.jda.2013.08.002 doi: 10.1016/j.jda.2013.08.002
[19]	D. Mondal, R. I. Nishat, S. Whitesides, M. S. Rahman, Acyclic colorings of graph subdivisions, In: C. S. Iliopoulos, W. F. Smyth, IWOCA 2011: Combinatorial algorithms, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-25011-8_20
[20]	D. R. Wood, Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. Theor. Comput. Sci., 7 (2005), 37–50.
[21]	R. E. Jamison, G. L. Matthews, Acyclic colorings of products of cycles, Bull. Inst. Combin. Appl., 54 (2008), 59–76.
[22]	R. E. Jamison, G. L. Matthews, On the acyclic chromatic number of hamming graphs, Graph Combinator., 24 (2008), 349–360. https://doi.org/10.1007/s00373-008-0798-4 doi: 10.1007/s00373-008-0798-4
[23]	R. E. Jamison, G. L. Matthews, J. Villalpando, Acyclic colorings of products of trees, Inform. Process. Lett., 99 (2006), 7–12. https://doi.org/10.1016/j.ipl.2005.11.023 doi: 10.1016/j.ipl.2005.11.023
[24]	S. Špacapan, A. Horvat, On acyclic colorings of direct products, Discuss. Math. Graph Theory, 28 (2008), 323–333. https://doi.org/10.7151/dmgt.1408 doi: 10.7151/dmgt.1408
[25]	W. Szumny, I. Włoch, A. Włoch, On the existence and on the number of $(k, 1)-$kernels in the lexicographic product of graphs, Discrete Math., 308 (2008), 4616–4624. https://doi.org/10.1016/j.disc.2007.08.078 doi: 10.1016/j.disc.2007.08.078
[26]	T. Karthick, Star coloring of certain graph classes, Graph Combinator., 34 (2018), 109–128. https://doi.org/10.1007/s00373-017-1864-6 doi: 10.1007/s00373-017-1864-6

Reader Comments

Your name:*

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