zbMATH — the first resource for mathematics

An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs. (English) Zbl 1383.05124
Summary: An adjacent vertex distinguishing total \(k\)-coloring of a graph \(G\) is a proper total \(k\)-coloring of \(G\) such that any pair of adjacent vertices have different sets of colors. The minimum number \(k\) needed for such a total coloring of \(G\) is denoted by \(\chi_a^{\prime \prime}(G)\). In this paper we prove that \(\chi_a^{\prime \prime}(G) \leq 2 \varDelta(G) - 1\) if \(\varDelta(G) \geq 4\), and \(\chi_a^{\prime \prime}(G) \leq \lceil \frac{5 \varDelta(G) + 8}{3} \rceil\) in general. This improves a result in D. Huang et al. [ibid. 312, No. 24, 3544–3546 (2012; Zbl 1258.05037)] which states that \(\chi_a^{\prime \prime}(G) \leq 2 \varDelta(G)\) for any graph with \(\varDelta(G) \geq 3\).

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Brooks, R. L., On coloring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-197, (1941) · JFM 67.0733.02
[2] 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
[3] Lu, Y.; Li, J.; Luo, R.; Miao, Z., Adjacent vertex distinguishing total coloring of graphs with maximum degree 4, Discrete Math., 340, 119-123, (2017) · Zbl 1351.05084
[4] Vizing, V. G., On an estimate of the chromatic class of a p-graph, Diskret. Anal., 3, 25-30, (1964), (in Russian)
[5] Vučković, B., Edge-partitions of graphs and their neighbor-distinguishing index, Discrete Math., 340, 3092-3096, (2017) · Zbl 1370.05175
[6] Wang, Y.; Wang, W.; Huo, J., Some bounds on the neighbor-distinguishing index of graphs, Discrete Math., 338, 2006-2013, (2015) · Zbl 1314.05082
[7] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On the adjacent vertex distinguishing total coloring of graphs, Sci. China Ser. A, 48, 3, 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.