×

zbMATH — the first resource for mathematics

Adjacent vertex distinguishing total colorings of 2-degenerate graphs. (English) Zbl 1339.05141
Summary: Let \(\phi\) be a proper total coloring of \(G\). We use \(C_\phi(v) = \{\phi(v) \} \cup \{\phi(u v) \mid u v \in E(G) \}\) to denote the set of colors assigned to a vertex \(v\) and those edges incident with \(v\). An adjacent vertex distinguishing total coloring of a graph \(G\) is a proper total coloring of \(G\) such that \(C_\phi(u) \neq C_\phi(v)\) for any \(u v \in E(G)\). The minimum number of colors required for an adjacent vertex distinguishing total coloring of \(G\) is denoted by \(\chi_a^{\prime\prime}(G)\). In this paper we show that if \(G\) is a 2-degenerate graph, then \(\chi_a^{\prime\prime}(G) \leq \max \{\varDelta(G) + 2, 6 \}\). Moreover, we also show that when \(\varDelta \geq 5\), \(\chi_a^{\prime\prime}(G) = \Delta(G) + 2\) if and only if \(G\) contains two adjacent vertices of maximum degree. Our results imply the results on outerplanar graphs, \(K_4\)-minor free graphs and graphs with maximum average degree less than 3.

MSC:
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balister, P.; Bollobás, B.; Schelp, R., Vertex distinguishing colorings of graphs with \(\Delta = 2\), Discrete Math., 252, 2, 17-29, (2002) · Zbl 1005.05019
[2] Bazgan, C.; Harkat-Benhamdine, A.; Li, H.; Woźniak, M., On the vertex-distinguishing proper edge-coloring of graphs, J. Combin. Theory Ser. B, 75, 2, 288-301, (1999) · Zbl 0932.05036
[3] Burris, A.; Schelp, R., Vertex-distinguishing proper edge-colorings, J. Graph Theory, 26, 2, 73-82, (1997) · Zbl 0886.05068
[4] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta = 3\), Discrete Math., 308, 17, 4003-4007, (2008) · Zbl 1203.05052
[5] Huang, D.; Wang, W.; Yan, C., A note on the adjacent vertex distinguishing total chromatic number of graphs, Discrete Math., 312, 24, 3544-3546, (2012) · Zbl 1258.05037
[6] Hulgan, J., Concise proofs for adjacent vertex-distinguishing total colorings, Discrete Math., 309, 2548-2550, (2009) · Zbl 1221.05143
[7] Wang, H., On the adjacent vertex distinguishing total chromatic number of the graphs with \(\Delta = 3\), J. Comb. Optim., 14, 87-109, (2007) · Zbl 1125.05043
[8] Wang, Y.; Cheng, J.; Luo, R.; Mulley, G., Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs, J. Comb. Optim., 143, 12, 1-7, (2014)
[9] Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim., 27, 2, 379-396, (2014) · Zbl 1319.90076
[10] Wang, W.; Wang, Y., Adjacent vertex distinguishing total coloring of graphs with lower average degree, Taiwanese J. Math., 12, 4, 979-990, (2008) · Zbl 1168.05023
[11] Wang, W.; Wang, P., On adjacent-vertex-distinguishing total coloring of \(K_4\)-minor free graphs, Sci. China Ser. A, 39, 12, 1462-1472, (2009), (in Chinese)
[12] Wang, Y.; Wang, W., Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Comb. Optim., 19, 123-133, (2010) · Zbl 1216.05039
[13] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A, 48, 289-299, (2005) · Zbl 1080.05036
[14] Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15, 5, 623-626, (2002) · Zbl 1008.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.