# zbMATH — the first resource for mathematics

Asymptotically optimal neighbor sum distinguishing total colorings of graphs. (English) Zbl 1351.05083
Summary: Given a proper total $$k$$-coloring $$c : V(G) \cup E(G) \rightarrow \{1,2,\ldots,k\}$$ of a graph $$G$$, we define the value of a vertex $$v$$ to be $$c(v) + \sum_{u v \in E(G)} c(u v)$$. The smallest integer $$k$$ such that $$G$$ has a proper total $$k$$-coloring whose values form a proper coloring is the neighbor sum distinguishing total chromatic number of $$G$$, $$\chi_\Sigma^{\prime \prime}(G)$$. M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] conjectured that $$\chi_\Sigma^{\prime \prime}(G) \leq \Delta(G) + 3$$ for any simple graph with maximum degree $$\Delta(G)$$. In this paper, we prove this bound to be asymptotically correct by showing that $$\chi_\Sigma^{\prime \prime}(G) \leq \Delta(G)(1 + o(1))$$. The main idea of our argument relies on Przybyło’s proof [J. Przybyło’s, Random Struct. Algorithms 47, No. 4, 776–791 (2015; Zbl 1331.05083)] regarding neighbor sum distinguishing edge-colorings.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Alon, N.; Spencer, J. H., (The Probabilistic Method, Wiley Series in Discrete Mathematics and Optimization, (2011), Wiley)  Behzad, Mehdi, Graphs and their chromatic numbers, (1965), ProQuest LLC, Ann Arbor, MI, Michigan State University, (Ph.D. thesis)  Chartrand, Gary; Erdős, Paul; Oellermann, Ortrud R., How to define an irregular graph, College Math. J., 19, 1, 36-42, (1988) · Zbl 0995.05516  Chartrand, Gary; Jacobson, Michael S.; Lehel, Jenő; Oellermann, Ortrud R.; Ruiz, Sergio; Saba, Farrokh, Irregular networks, Congr. Numer., 64, 197-210, (1988), 250th Anniversary Conference on Graph Theory (Fort Wayne, IN, 1986) · Zbl 0671.05060  Dong, AiJun; Wang, GuangHui, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin. (Engl. Ser.), 30, 4, 703-709, (2014) · Zbl 1408.05061  Flandrin, Evelyne; Marczyk, Antoni; Przybyło, Jakub; Saclé, Jean-François; Woźniak, Mariusz, Neighbor sum distingishing index, Graphs Combin., 29, 5, 1329-1336, (2013) · Zbl 1272.05047  Gallian, J. A., Graph labeling, Electron. J. Combin, DS6, 1-389, (2015)  Li, Hualong; Ding, Laihao; Liu, Bingqiang; Wang, Guanghui, Neighbor sum distinguishing total colorings of planar graphs, J. Combin. Optim., 1-14, (2013) · Zbl 1306.05066  Li, Hualong; Liu, Bingqiang; Wang, Guanghui, Neighbor sum distinguishing total colorings of $$K_4$$-minor free graphs, Front. Math. China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066  Molloy, Michael; Reed, Bruce, A bound on the total chromatic number, Combinatorica, 18, 2, 241-280, (1998) · Zbl 0921.05033  Molloy, Michael; Reed, Bruce, Near-optimal List colorings, (Proceedings of the Ninth International Conference, “Random Structures and Algorithms” (Poznan, 1999), Vol. 17, (2000)), 376-402 · Zbl 0971.05047  Molloy, M.; Reed, B., (Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, (2002), Springer) · Zbl 0987.05002  Pilśniak, Monika; Woźniak, Mariusz, On the total-neighbor-distinguishing index by sums, Graphs Combin., 1-12, (2013) · Zbl 1312.05054  Przybyło, Jakub, Asymptotically optimal neighbour sum distinguishing colourings of graphs, Random Structures Algorithms, 47, 4, 776-791, (2015) · Zbl 1331.05083  Vizing, V. G., Some unsolved problems in graph theory, Uspekhi Mat. Nauk, 23, 6(144), 117-134, (1968) · Zbl 0177.52301  Wang, JiHui; Ma, QiaoLing; Han, Xue, Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sin. (Engl. Ser.), 31, 2, 216-224, (2015) · Zbl 1317.05065  Xu, Renyu; Wu, Jianliang; Xu, Jin, Neighbor sum distinguishing total coloring of graphs embedded in surfaces of nonnegative Euler characteristic, J. Combin. Optim., 1-13, (2015)
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.