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:
 [1] Alon, N.; Spencer, J. H., (The Probabilistic Method, Wiley Series in Discrete Mathematics and Optimization, (2011), Wiley) [2] Behzad, Mehdi, Graphs and their chromatic numbers, (1965), ProQuest LLC, Ann Arbor, MI, Michigan State University, (Ph.D. thesis) [3] 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 [4] 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 [5] 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 [6] 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 [7] Gallian, J. A., Graph labeling, Electron. J. Combin, DS6, 1-389, (2015) [8] 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 [9] 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 [10] Molloy, Michael; Reed, Bruce, A bound on the total chromatic number, Combinatorica, 18, 2, 241-280, (1998) · Zbl 0921.05033 [11] 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 [12] Molloy, M.; Reed, B., (Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, (2002), Springer) · Zbl 0987.05002 [13] Pilśniak, Monika; Woźniak, Mariusz, On the total-neighbor-distinguishing index by sums, Graphs Combin., 1-12, (2013) · Zbl 1312.05054 [14] Przybyło, Jakub, Asymptotically optimal neighbour sum distinguishing colourings of graphs, Random Structures Algorithms, 47, 4, 776-791, (2015) · Zbl 1331.05083 [15] Vizing, V. G., Some unsolved problems in graph theory, Uspekhi Mat. Nauk, 23, 6(144), 117-134, (1968) · Zbl 0177.52301 [16] 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 [17] 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.