AVD edge-colorings of cubic Halin graphs

Ningge Huang; Lily Chen; Ningge Huang; Lily Chen

doi:10.3934/math.20231423

AIMS Mathematics

2023, Volume 8, Issue 11: 27820-27839. doi: 10.3934/math.20231423

Previous Article Next Article

Research article

AVD edge-colorings of cubic Halin graphs

Ningge Huang ,
Lily Chen ^,

School of Mathematical Sciences, Huaqiao University, Quanzhou, China

Received: 25 June 2023 Revised: 11 September 2023 Accepted: 18 September 2023 Published: 09 October 2023
MSC : 05C15

The adjacent vertex-distinguishing edge-coloring of a graph $ G $ is a proper edge-coloring of $ G $ such that each pair of adjacent vetices receives a distinct set of colors. The minimum number of colors required in an adjacent vertex-distinguishing edge-coloring of $ G $ is called the adjacent vertex-distinguishing chromatic index. In this paper, we determine the adjacent vertex distinguishing chromatic indices of cubic Halin graphs whose characteristic trees are caterpillars.
- AVD edge-coloring,
- adjacent vertex-distinguishing chromatic index,
- Halin graphs,
- cubic graphs
Citation: Ningge Huang, Lily Chen. AVD edge-colorings of cubic Halin graphs[J]. AIMS Mathematics, 2023, 8(11): 27820-27839. doi: 10.3934/math.20231423

Related Papers:

Abstract

The adjacent vertex-distinguishing edge-coloring of a graph $ G $ is a proper edge-coloring of $ G $ such that each pair of adjacent vetices receives a distinct set of colors. The minimum number of colors required in an adjacent vertex-distinguishing edge-coloring of $ G $ is called the adjacent vertex-distinguishing chromatic index. In this paper, we determine the adjacent vertex distinguishing chromatic indices of cubic Halin graphs whose characteristic trees are caterpillars.

References

[1]	Z. F. Zhang, L. Z. Liu, J. F. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15 (2002), 623–626. https://doi.org/10.1016/S0893-9659(02)80015-5 doi: 10.1016/S0893-9659(02)80015-5
[2]	P. N. Balister, E. Györi, J. Lehel, R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21 (2007), 237–250. https://doi.org/10.1137/S0895480102414107 doi: 10.1137/S0895480102414107
[3]	H. Hatami, $\Delta+300$ is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B, 95 (2005), 246–256. https://doi.org/10.1016/j.jctb.2005.04.002 doi: 10.1016/j.jctb.2005.04.002
[4]	G. Joret, W. Lochet, Progress on the adjacent vertex distinguishing edge coloring conjecture, SIAM J. Discrete Math., 34 (2020), 2221–2238. https://doi.org/10.1137/18M1200427 doi: 10.1137/18M1200427
[5]	M. Horňák, D. J. Huang, W. F. Wang, On neighbor-distinguishing index of planar graphs, J. Graph Theory, 76 (2014), 262–278. https://doi.org/10.1002/jgt.21764 doi: 10.1002/jgt.21764
[6]	X. W. Yu, C. Q. Qu, G. H. Wang, Y. Q. Wang, Adjacent vertex distinguishing colorings by sum of sparse graphs, Discrete Math., 339 (2016), 62–71. https://doi.org/10.1016/j.disc.2015.07.011 doi: 10.1016/j.disc.2015.07.011
[7]	H. Hocquard, M. Montassier, Adjacent vertex-distinguishing edge coloring of graphs with maximum degree $\Delta$, J. Comb. Optim., 26 (2013), 152–160. https://doi.org/10.1007/s10878-011-9444-9 doi: 10.1007/s10878-011-9444-9
[8]	M. Bonamy, J. Przybyło, On the neighbor sum distinguishing index of planar graphs, J. Graph Theroy, 85 (2017), 669–690. https://doi.org/10.1002/jgt.22098 doi: 10.1002/jgt.22098
[9]	D. J. Huang, Z. K. Miao, W. F. Wang, Adjacent vertex distinguishing indices of planar graphs without 3-cycles, Discrete Math., 338 (2015), 139–148. https://doi.org/10.1016/j.disc.2014.10.010 doi: 10.1016/j.disc.2014.10.010
[10]	Y. Wang, J. Cheng, R. Luo, G. Mulley, Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs, J. Comb. Optim., 31 (2016), 874–880. https://doi.org/10.1007/s10878-014-9796-z doi: 10.1007/s10878-014-9796-z
[11]	W. F. Wang, Y. Q. Wang, Adjacent vertex-distinguishing edge coloring of $K_4$-minor free graphs, Appl. Math. Lett., 24 (2011), 2034–2037. https://doi.org/10.1016/j.aml.2011.05.038 doi: 10.1016/j.aml.2011.05.038
[12]	G. J. Chang, D. D. Liu, Strong edge-coloring for cubic Halin graphs, Discrete Math., 312 (2012), 1468–1475. https://doi.org/10.1016/j.disc.2012.01.014 doi: 10.1016/j.disc.2012.01.014

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)