Article in press
Authors:
Title:
Adjacent vertex strongly distinguishing total coloring of graphs with lower average degree
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-08-30 , Revised: 2023-08-11 , Accepted: 2023-08-11 , Available online: 2023-09-25 , https://doi.org/10.7151/dmgt.2518
Abstract:
An adjacent vertex strongly distinguishing total-coloring of a graph $G$
is a proper total-coloring such that no two adjacent vertices meet the
same color set, where the color set of a vertex consists of all colors assigned
on the vertex and its incident edges and neighbors. The minimum number of the
colors required is called adjacent vertex strongly distinguishing total
chromatic number, denoted by $\chi_{ast}(G)$. Let mad$(G)$ and $\Delta(G)$
denote the maximum average degree and the maximum degree of graph $G$,
respectively. In this paper, we prove the following results. (1) If $G$ is a
graph with mad$(G)$$<\frac{7}{3}$ and $\Delta(G)\geq5$, then $\chi_{ast}(G)
\leq\max\{\Delta(G)+2, 8\}$. (2) If $G$ is a graph with mad$(G)$$<\frac{9}{4}$
and $4\leq\Delta(G)\leq5$, then $\chi_{ast}(G)\leq\Delta(G)+2$. (3) If $G$ is a
graph with mad$(G)$$<\frac{9}{4}$ and $\Delta(G)=3$, then $\chi_{ast}(G)\leq6$.
Keywords:
total-coloring,discharging method
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press, New York, 1976).
- Y.L. Chang, J. Hu, G.H. Wang and X. Yu, Adjacent vertex distinguishing total coloring of planar graphs with maximum degree $8$, Discrete Math. 343(10) (2020) 112014.
https://doi.org/10.1016/j.disc.2020.112014 - X.E. 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 - D.J. Huang, X.X. Zhang, W.F. Wang and S. Finbow, Adjacent vertex distinguishing edge coloring of planar graphs without $3$-cycles, Discrete Math. Algorithms Appl. 12(4) (2020) 2050035.
https://doi.org/10.1142/S1793830920500354 - 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 - Z.K. Miao, R. Shi, X.L. Hu and R. Luo, Adjacent vertex distinguishing total colorings of $2$-degenerate graphs, Discrete Math. 339 (2016) 2446–2449.
https://doi.org/10.1016/j.disc.2016.03.019 - M. Montassier and A. Raspaud, $(d,1)$-total labeling of graphs with a given maximum average degree, J. Graph Theory 51 (2006) 93–109.
https://doi.org/10.1002/jgt.20124 - S.L. Tian and Q. Wang, Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs, Discrete Appl. Math. 185 (2015) 220–226.
https://doi.org/10.1016/j.dam.2014.11.028 - W.F. Wang and D.J. 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.F. Wang and Y.Q. Wang, Adjacent vertex distinguishing total coloring of graphs with lower average degree, Taiwanese J. Math. 12 (2008) 979–990.
https://doi.org/10.11650/twjm/1500404991 - W.F. Wang and 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 - C.C. Yan, D.J. Huang, D. Chen and W.F. Wang, Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five, J. Comb. Optim. 28 (2014) 893–909.
https://doi.org/10.1007/s10878-012-9569-5 - C.C. Yang, H. Ren and B. Yao, Adjacent vertex distinguishing total colorings of graphs with four distinguishing constraints, Ars Combin. 127 (2016) 197–208.
- S.J. Zhang, X.E. Chen and X.S. Liu, Adjacent-vertex-distinguishing total chromatic numbers on $2$-connected outer plane graphs with $\Delta=5$, J. Northwest Normal University (Natural Science) 41 (2005) 8–13, in Chinese.
https://doi.org/10.16783/j.cnki.nwnuz.2005.05.003 - Z.F. Zhang, X.E. Chen, J.W. Li, B. Yao, X.Z. Lu and J.F. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Math. 48 (2005) 289–299.
https://doi.org/10.1360/03ys0207 - Z.F. Zhang, H. Cheng, B. Yao, J.W. Li, X.E. Chen and B.G. Xu, On the adjacent-vertex-strongly-distinguishing total coloring of graphs, Sci. China Math. 51 (2008) 427–436.
https://doi.org/10.1007/s11425-007-0128-y
Close