Article in volume
Authors:
Title:
Adjacent vertex distinguishing total coloring of the corona product of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 317-335
Received: 2020-04-21 , Revised: 2021-12-23 , Accepted: 2021-12-28 , Available online: 2022-01-12 , https://doi.org/10.7151/dmgt.2445
Abstract:
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)\neq C(v)$, where $C(u)$ is the set of colors given
to vertex $u$ and the edges incident to $u$ for $u\in V(G)$. The AVD-total
chromatic number, $\chi''_{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 $\Delta$,
$\chi''_{a}(G)\leq\Delta+3$. The total coloring conjecture states that for any
graph $G$ with maximum degree $\Delta$, $\chi''(G)\leq \Delta+2$, where
$\chi''(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 $\Delta(H)\leq \Delta(G)$, the corona product $G\circ H$ of $G$ and
$H$ satisfies the AVD-total coloring conjecture. We also prove that the graph
$G\circ K_n$ admits an AVD-total coloring using $(\Delta(G\circ K_n)+p)$ colors,
if there is an AVD-total coloring of graph $G$ using $(\Delta(G)+p)$ colors,
where $p\in \{1,2,3\}$. Furthermore, given a total colorable graph $G$ and
positive integer $r$ and $p$ where $1\leq p\leq 3$, we classify the corona
graphs $G^{(r)}=G\circ G\circ \cdots \circ G\ (r+1 \mbox{ times} )$ such that
$\chi_a''(G^{(r)})=\Delta(G^{(r)})+p$.
Keywords:
adjacent vertex distinguishing total coloring, corona products
References:
- M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. Thesis (Michigan State University, Dept. of Mathematics, 1965).
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - S. Mohan, J. Geetha and K. Somusundaram, Total coloring of the corona product of two graphs, Australas. J. Combin. 68 (2017) 15–22.
- 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 - 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 - V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25–30.
- 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 - 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 - 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 - D.B. West, Introduction to Graph Theory, 2 Ed. (Prentice Hall, Upper Saddle River, 2001).
- 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 - 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
Close