Geodesic
Adjacent vertex distinguishing total coloring of the corona product of graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 317-335 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

An adjacent vertex distinguishing (AVD-)total coloring of a simple graph G is a proper total coloring of G such that for any pair of adjacent vertices u and v, we have C(u) C(v), where C(u) is the set of colors given to vertex u and the edges incident to u for u∈ V(G). The AVD-total chromatic number, χ_a^” (G), of a graph G is the minimum number of colors required for an AVD-total coloring of G. The AVD-total coloring conjecture states that for any graph G with maximum degree Δ, χ_a^” (G) ≤Δ+3. The total coloring conjecture states that for any graph G with maximum degree Δ, χ^” (G) ≤Δ+2, where χ^” (G) is the total chromatic number of G, that is, the minimum number of colors needed for a proper total coloring of G. A graph G is said to be AVD-total colorable (total colorable) graph, if G satisfies the AVD-total coloring conjecture (total coloring conjecture). In this paper, we prove that for any AVD-total colorable graph G and any total-colorable graph H with Δ(H)≤Δ(G), the corona product G∘ H of G and H satisfies the AVD-total coloring conjecture. We also prove that the graph G∘ K_n admits an AVD-total coloring using (Δ(G∘ K_n)+p) colors, if there is an AVD-total coloring of graph G using (Δ(G)+p) colors, where p∈{1,2,3}. Furthermore, given a total colorable graph G and positive integer r and p where 1≤ p≤ 3, we classify the corona graphs G^(r)=G∘ G∘⋯∘ G (r+1 ) such that χ_a^” (G^(r))=Δ(G^(r))+p.
Keywords: adjacent vertex distinguishing total coloring, corona products 
@article{DMGT_2024_44_1_a15,
     author = {Verma, Shaily and Panda, B. S.},
     title = {Adjacent vertex distinguishing total coloring of the corona product of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {317--335},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a15/}
}
TY  - JOUR
AU  - Verma, Shaily
AU  - Panda, B. S.
TI  - Adjacent vertex distinguishing total coloring of the corona product of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 317
EP  - 335
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a15/
LA  - en
ID  - DMGT_2024_44_1_a15
ER  - 
%0 Journal Article
%A Verma, Shaily
%A Panda, B. S.
%T Adjacent vertex distinguishing total coloring of the corona product of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 317-335
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a15/
%G en
%F DMGT_2024_44_1_a15
Verma, Shaily; Panda, B. S. Adjacent vertex distinguishing total coloring of the corona product of graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 317-335. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a15/

[1] M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. Thesis (Michigan State University, Dept. of Mathematics, 1965).

[2] X. Chen, On the adjacent vertex distinguishing total coloring numbers of graphs with \Delta=3, Discrete Math. 308 (2008) 4003–4007. https://doi.org/10.1016/j.disc.2007.07.091

[3] X. Cheng, G. Wang and J. Wu, The adjacent vertex distinguishing total chromatic numbers of planar graphs with \Delta = 10, J. Comb. Optim. 34 (2017) 383–397. https://doi.org/10.1007/s10878-016-9995-x

[4] J. Hu, G. Wang, J. Wu, D. Yang and X. Yu, Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 9, Discrete Math. 342 (2019) 1392–1402. https://doi.org/10.1016/j.disc.2019.01.024

[5] D. Huang and W. Wang, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci. Sin. Math. 42 (2012) 151–164. https://doi.org/10.1360/012011-359

[6] 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

[7] J. Huo, W. Wang and Y. Wang, A characterization for the neighbor-distinguishing total chromatic number of planar graphs with \Delta=13, Discrete Math. 341 (2018) 3044–3056. https://doi.org/10.1016/j.disc.2018.07.011

[8] Y. Lu, J. Li, R. Luo and Z. Miao, Adjacent vertex distinguishing total coloring of graphs with maximum degree 4, Discrete Math. 340 (2017) 119–123. https://doi.org/10.1016/j.disc.2016.07.011

[9] A.G. Luiz, C.N. Campos and C.P. de Mello, AVD-total-chromatic number of some families of graphs with \Delta(G)=3, Discrete Appl. Math. 217 (2017) 628–638. https://doi.org/10.1016/j.dam.2016.09.041

[10] C.J.H. McDiarmid and A. Sánchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994) 155–162. https://doi.org/10.1016/0012-365X(92)00058-Y

[11] S. Mohan, J. Geetha and K. Somusundaram, Total coloring of the corona product of two graphs, Australas. J. Combin. 68 (2017) 15–22.

[12] A. Papaioannou and C. Raftopoulou, On the AVDTC of 4-regular graphs, Discrete Math. 330 (2014) 20–40. https://doi.org/10.1016/j.disc.2014.03.019

[13] R. Vignesh, J. Geetha and K. Somusundaram, Total coloring conjecture for vertex, edge and neighborhood corona products of graphs, Discrete Math. Algorithms Appl. 11 (2019) 1950014. https://doi.org/10.1142/S1793830919500149

[14] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25–30.

[15] H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \Delta(G)=3, J. Comb. Optim. 14 (2007) 87–109. https://doi.org/10.1007/s10878-006-9038-0

[16] W. Wang and D. Huang, The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim. 27 (2014) 379–396. https://doi.org/10.1007/s10878-012-9527-2

[17] W. Wang, J. Huo, D. Huang and Y. Wang, Planar graphs with \Delta = 9 are neighbor-distinguishing totally 12-colorable, J. Comb. Optim. 37 (2019) 1071–1089. https://doi.org/10.1007/s10878-018-0334-2

[18] D.B. West, Introduction to Graph Theory, 2 Ed. (Prentice Hall, Upper Saddle River, 2001).

[19] D. Yang, L. Sun, X. Yu, J. Wu and S. Zhou, Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10, Appl. Math. Comput. 314 (2017) 456–468. https://doi.org/10.1016/j.amc.2017.06.002

[20] Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu and J. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A 48 (2005) 289–299. https://doi.org/10.1360/03ys0207