×

zbMATH — the first resource for mathematics

Upper bounds on adjacent vertex distinguishing total chromatic number of graphs. (English) Zbl 1372.05073
Summary: An adjacent vertex distinguishing total coloring of a graph \(G\) is a proper total coloring of \(G\) such that for any pair of adjacent vertices, the set of colors appearing on the vertex and incident edges are different. The minimum number of colors required for an adjacent vertex distinguishing total coloring of \(G\) is denoted by \(\chi_a^{\prime\prime}(G)\). Let \(G\) be a graph, and \(\chi(G)\) and \(\chi^\prime(G)\) be the chromatic number and edge chromatic number of \(G\), respectively. In this paper we show that \(\chi_a^{\prime\prime}(G)\leq \chi(G)+\chi^\prime(G)-1\) for any graph \(G\) with \(\chi(G)\geq 6\), and \(\chi_a^{\prime\prime}(G)\leq \chi(G)+\varDelta(G)\) for any graph \(G\). Our results improve the only known upper bound \(2\varDelta\) obtained by D. Huang et al. [Discrete Math. 312, No. 24, 3544–3546 (2012; Zbl 1258.05037)]. As a direct consequence, we have \(\chi_a^{\prime\prime}(G)\leq \varDelta(G)+3\) if \(\chi(G)=3\) and thus it implies the known results on graphs with maximum degree 3, \(K_4\)-minor-free graphs, outerplanar graphs, graphs with maximum average degree less than 3, planar graphs with girth at least 4 and 2-degenerate graphs.
MSC:
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, K.; Haken, W., Every planar map is four colorable, Bull. Amer. Math. Soc., 82, 711-712, (1976) · Zbl 0331.05106
[2] 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
[3] Grötzsch, H., Zur theorie der diskreten gebilde. VII. ein dreifarbensatz für dreikreisfreie netze auf der kugel. (German), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Natur. Reih., 8, 109-120, (1958/1959)
[4] 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
[5] Hulgan, J., Concise proofs for adjacent vertex-distinguishing total colorings, Discrete Math., 309, 2548-2550, (2009) · Zbl 1221.05143
[6] Miao, Z.; Shi, R.; Hu, X.; Luo, R., Adjacent vertex distinguishing total colorings of 2-degenerate graphs, Discrete Math., 339, 2446-2449, (2016) · Zbl 1339.05141
[7] Vizing, V., On an estimate of the chromatic index of a \(p\)-graph, Diskret. Anal., 3, 25-30, (1964)
[8] 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
[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
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.