# zbMATH — the first resource for mathematics

Neighbor sum distinguishing total choosability of planar graphs. (English) Zbl 1348.05082
Summary: A total-$$k$$-coloring of a graph $$G$$ is a mapping $$c:V(G)\cup E(G)\to\{1,2,\dots,k\}$$ such that any two adjacent or incident elements in $$V(G)\cup E(G)$$ receive different colors. For a total-$$k$$-coloring of $$G$$, let $$\sum_c(v)$$ denote the total sum of colors of the edges incident with $$v$$ and the color of $$v$$. If for each edge $$uv\in E(G)$$, $$\sum_c(u)\neq\sum_c(v)$$, then we call such a total-$$k$$-coloring neighbor sum distinguishing. The least number $$k$$ needed for such a coloring of $$G$$ is the neighbor sum distinguishing total chromatic number, denoted by $$\chi^{\prime\prime}_\Sigma(G)$$. Pilśniak and Woźniak conjectured $$\chi^{\prime\prime}_\Sigma(G)\leq\Delta (G)+3$$ for any simple graph with maximum degree $$\Delta (G)$$. In this paper, we prove that for any planar graph $$G$$ with maximum degree $$\Delta (G)$$, $$\mathrm{ch}^{\prime\prime}_\Sigma(G)\leq\max\{\Delta (G)+3,16\}$$, where $$\mathrm{ch}^{\prime\prime}_\Sigma(G)$$ is the neighbor sum distinguishing total choosability of $$G$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text:
##### References:
  Alon, N, Combinatorial nullstellensatz, Combin Probab Comput, 8, 7-29, (1999) · Zbl 0920.05026  Bondy JA, Murty USR (1976) Graph theory with applications. Elsevier, North-Holland · Zbl 1226.05083  Borodin, OV; Kostochka, AV; Woodall, DR, List edge and List total colourings of multigraphs, J Combin Theory Ser B, 71, 184-204, (1997) · Zbl 0876.05032  Chartrand, G; Jacobson, M; Lehel, J; Oellermann, O; Ruiz, S; Saba, F, Irregular networks, Congr Numer, 64, 197-210, (1988) · Zbl 0671.05060  Cheng X, Huang D, Wang G, Wu J (2015) Neighbor sum distinguishing total colorings of planar graphs with maximum degree $$Δ$$. Discrete Appl. Math. doi:10.1016/j.dam.2015.03.013 · Zbl 1316.05041  Coker, T; Johannson, K, The adjacent vertex distinguishing total chromatic number, Discrete Math, 312, 741-2750, (2012) · Zbl 1245.05042  Ding, L; Wang, G; Yan, G, Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci China Math, 57, 1875-1882, (2014) · Zbl 1303.05058  Ding L, Wang G, Wu J, Yu J (submitted) Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz · Zbl 1371.05078  Dong, A; Wang, G, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math Sinica, 30, 703-709, (2014) · Zbl 1408.05061  Huang, D; Wang, W; Yan, C, A note on the adjacent vertex distinguishing total chromatic number of graphs, Discrete Math, 312, 3544-3546, (2012) · Zbl 1258.05037  Huang, P; Wong, T; Zhu, X, Weighted-1-antimagic graphs of prime power order, Discrete Math, 312, 2162-2169, (2012) · Zbl 1244.05186  Kalkowski, M; Karoński, M; Pfender, F, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J Combin Theory Ser B, 100, 347-349, (2010) · Zbl 1209.05087  Li H, Ding L, Liu B, Wang G (2013) Neighbor sum distinguishing total colorings of planar graphs. J Comb Optim. doi:10.1007/s10878-013-9660-6 · Zbl 1325.05083  Li, H; Liu, B; Wang, G, Neighor sum distinguishing total colorings of $$K_{4}$$-minor free graphs, Front Math China, 8, 1351-1366, (2013) · Zbl 1306.05066  Pilśniak M, Woźniak M (2013) On the total-neighbor-distinguishing index by sums. Graphs Combin. doi:10.1007/s00373-013-1399-4 · Zbl 1303.05058  Przybyło, J, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J Discrete Math, 23, 511-516, (2009) · Zbl 1216.05135  Przybyło, J; Woźniak, M, On a 1,2 conjecture, Discrete Math Theor Comput Sci, 12, 101-108, (2010) · Zbl 1250.05093  Przybyło, J; Woźniak, M, Total weight choosability of graphs, Electronic J Combin, 18, p112, (2011) · Zbl 1217.05202  Scheim, E, The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Math, 8, 377-382, (1974) · Zbl 0281.05103  Wang, W; Huang, D, The adjacent vertex distinguishing total coloring of planar graphs, J Combin Optim, 27, 379-396, (2014) · Zbl 1319.90076  Wang, W; Wang, P, On adjacent-vertex- distinguishing total coloring of $$K_4$$-minor free graphs, Sci China Ser A, 39, 1462-1472, (2009)  Wong, T; Zhu, X, Total weight choosability of graphs, J Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161  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.