Distinguishing colorings of graphs and their subgraphs

Baolin Ma; Chao Yang; Baolin Ma; Chao Yang

doi:10.3934/math.20231357

AIMS Mathematics

2023, Volume 8, Issue 11: 26561-26573. doi: 10.3934/math.20231357

Previous Article Next Article

Research article

Distinguishing colorings of graphs and their subgraphs

Baolin Ma ^{1
,
,},
Chao Yang ²

1.
School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang, 453003, China
2.
Center of Intelligent Computing and Applied Statistics, School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai, 201620, China

Received: 15 June 2023 Revised: 16 August 2023 Accepted: 01 September 2023 Published: 18 September 2023
MSC : 05C15

In this paper, several distinguishing colorings of graphs are studied, such as vertex distinguishing proper edge coloring, adjacent vertex distinguishing proper edge coloring, vertex distinguishing proper total coloring, adjacent vertex distinguishing proper total coloring. Finally, some related chromatic numbers are determined, especially the comparison of the correlation chromatic numbers between the original graph and the subgraphs are obtained.
Citation: Baolin Ma, Chao Yang. Distinguishing colorings of graphs and their subgraphs[J]. AIMS Mathematics, 2023, 8(11): 26561-26573. doi: 10.3934/math.20231357

Related Papers:

Abstract

In this paper, several distinguishing colorings of graphs are studied, such as vertex distinguishing proper edge coloring, adjacent vertex distinguishing proper edge coloring, vertex distinguishing proper total coloring, adjacent vertex distinguishing proper total coloring. Finally, some related chromatic numbers are determined, especially the comparison of the correlation chromatic numbers between the original graph and the subgraphs are obtained.

References

[1]	J. A. Bondy, U. S. R. Murty, Graph theory, London: Springer, 2008.
[2]	A. C. Burris, R. H. Schelp, Vertex-distinguishing proper edge-colorings, J. Graph Theory, 26 (1997), 73–82.
[3]	J. Ĉerný, M. Hor${\rm{\hat{n}}}$ák, R. Soták, Observability of a graph, Math. Slovaca, 46 (1996), 21–31.
[4]	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
[5]	Z. F. Zhang, J. W. Li, X. E. Chen, B. Yao, W. J. Wang, P. X. Qiu, $D(\beta)$-vertex-distinguishing total coloring of graphs, Sci. China Ser. A-Math., 49 (2006), 1430–1440.
[6]	Z. F. Zhang, X. E. Chen, J. W. Li, B. Yao, X. Z. Lu, J. F. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A-Math., 48 (2005), 289–299. https://doi.org/10.1360/03ys0207 doi: 10.1360/03ys0207
[7]	C. Bazgan, A. Harkat-Benhamdine, H. Li, M. Woźniak, On the vertex-distinguishing proper edge-colorings of graphs, J. Comb. Theory Ser. B, 75 (1999), 288–301. https://doi.org/10.1006/jctb.1998.1884 doi: 10.1006/jctb.1998.1884
[8]	A. C. Burris, Vertex-distinguishing edge-colorings, Memphis State Univ., 1993.
[9]	J. Hulgan, Concise proofs for adjacent vertex distinguishing total colorings, Discrete Math., 309 (2009), 2548–2550. https://doi.org/10.1016/j.disc.2008.06.002 doi: 10.1016/j.disc.2008.06.002
[10]	P. N. Balister, B. Bollob$\acute{a}$s, R. H. Schelp, Vertex distinguishing colorings of graphs with $\Delta(G) = 2$, Discrete Math., 252 (2002), 17–29. https://doi.org/10.1016/S0012-365X(01)00287-4 doi: 10.1016/S0012-365X(01)00287-4
[11]	W. F. Wang, Y. Q. Wang, Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree, J. Comb. Optim., 19 (2010), 471–485. https://doi.org/10.1007/s10878-008-9178-5 doi: 10.1007/s10878-008-9178-5
[12]	S. Akbafi, H. Bidkhori, N. Nosrati, $r$-Strong edge coloring of graphs, Discrete Math., 306 (2006), 3005–3010. https://doi.org/10.1016/j.disc.2004.12.027 doi: 10.1016/j.disc.2004.12.027
[13]	P. N. Balister, Vertex-distinguishing edge colorings of random graphs, Random Struct. Algor., 20 (2001), 89–97. https://doi.org/10.1002/rsa.10002 doi: 10.1002/rsa.10002
[14]	C. Bazgan, A. Harkat-Benhamdine, H. Li, M. Woźniak, A note on the vertex-distinguishing proper coloring of graphs with large minimum degree, Discrete Math., 236 (2001), 37–42. https://doi.org/10.1016/S0012-365X(00)00428-3 doi: 10.1016/S0012-365X(00)00428-3
[15]	E. Q. Zhu, C. J. Liu, A note on the vertex-distinguishing proper edge coloring of graphs, Ars Comb., 116 (2014), 93–99.
[16]	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
[17]	C. Greenhill, A. Ruciński, Neighbour-distinguishing edge colourings of random regular graphs, Electron J. Comb., 13 (2006), 875–903. https://doi.org/10.37236/1103 doi: 10.37236/1103
[18]	H. Hatami, $\Delta+300$ is a bound on the adjacent vertex distinguish edge chromatic number, J. Comb. 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
[19]	X. E. Chen, Z. F. Zhang, AVDTC numbers of generalized Halin graphs with maximum degree at Least 6, Acta Math. Appl. Sin-E, 24 (2008), 55–58. https://doi.org/10.1007/s10255-005-5222-8 doi: 10.1007/s10255-005-5222-8

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)