# zbMATH — the first resource for mathematics

Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz. (English) Zbl 1303.05058
Summary: Let $$G = (V,E)$$ be a graph and $$\phi$$ be a total coloring of $$G$$ by using the color set $$\{1, 2, \dots,k\}$$. Let $$f(v)$$ denote the sum of the color of the vertex $$v$$ and the colors of all incident edges of $$v$$. We say that $$\phi$$ is neighbor sum distinguishing if for each edge $$uv \in E(G)$$, $$f(u) \neq f(v)$$. The smallest number $$k$$ is called the neighbor sum distinguishing total chromatic number, denoted by $$\chi_{nsd}^{\prime\prime}(G)$$. M. Pilśniak and M. Woźniak [“On the adjacent-vertex-distinguishing index by sums in total paper colorings”, Preprint] conjectured that for any graph $$G$$ with at least two vertices, $$\chi_{nsd}^{\prime\prime}(G) \geqslant \Delta (G) + 3^{\prime\prime}$$. In this paper, by using the famous combinatorial nullstellensatz, we show that $$\chi_{nsd}^{\prime\prime}(G) \geqslant 2 \Delta (G)+\mathrm{col}(G)-1^{\prime\prime}$$, where $$\mathrm{col}(G)$$ is the coloring number of $$G$$. Moreover, we prove this assertion in its list version.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Alon, N, Combinatorial nullstellensatz, Combin Probab Comput, 8, 7-29, (1999) · Zbl 0920.05026  Bondy J A, Murty U S R. Graph Theory with Applications. New York: North-Holland, 1976 · Zbl 1226.05083  Chen, X E, On the adjacent vertex distinguishing total coloring numbers of graphs with δ = 3, Discrete Math, 308, 4003-4007, (2008) · Zbl 1203.05052  Cheng X H, Wu J L, Huang D J, et al. Neighbor sum distinguishing total colorings of planar graphs with maximum degree Δ. Submitted, 2013  Dong, A J; Wang, G H, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, (2013)  Huang, D J; Wang, W F, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree (in Chinese), Sci Sin Math, 42, 151-164, (2012)  Huang, P Y; Wong, T L; Zhu, X D, 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  Karoński, M; Łuczak, T; Thomason, A, Edge weights and vertex colors, J Combin Theory Ser B, 91, 151-157, (2004) · Zbl 1042.05045  Li, H L; Ding, L H; Liu, B Q; etal., Neighbor sum distinguishing total colorings of planar graphs, (2013)  Li, H L; Liu, B Q; Wang, G H, Neighbor 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. On the adjacent-vertex-distinguishing index by sums in total proper colorings. Preprint, http://www.ii.uj.edu.pl/preMD/index.php · Zbl 1216.05135  Przybyło, J, Irregularity strength of regular graphs, Electronic J Combin, 15, #r82, (2008) · Zbl 1163.05329  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, Neighbour distinguishing edge colorings via the combinatorial nullstellensatz, SIAM J Discrete Math, 27, 1313-1322, (2013) · Zbl 1290.05079  Przybyło, J; Woźniak, M, Total weight choosability of graphs, Electronic J Combin, 18, #p112, (2011) · Zbl 1217.05202  Przybyło, J; Woźniak, M, On a 1, 2 conjecture, Discrete Math Theor Comput Sci, 12, 101-108, (2010) · Zbl 1250.05093  Scheim, E, The number of edge 3-coloring of a planar cubic graph as a permanent, Discrete Math, 8, 377-382, (1974) · Zbl 0281.05103  Seamone B. The 1-2-3 conjecture and related problems: A survey. ArXiv:1211.5122, 2012  Wang, W F; Huang, D J, The adjacent vertex distinguishing total coloring of planar graphs, (2012)  Wang, W F; Wang, P, On adjacent-vertex-distinguishing total coloring of $$K$$_{4}-minor free graphs (in Chinese), Sci China Ser A, 39, 1462-1472, (2009)  Wang, Y Q; Wang, W F, Adjacent vertex distinguishing total colorings of outerplanar graphs, J Combin Optim, 19, 123-133, (2010) · Zbl 1216.05039  Wong, T L; Zhu, X D, Total weight choosability of graphs, J Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161  Wong, T L; Zhu, X D, Antimagic labelling of vertex weighted graphs, J Graph Theory, 3, 348-359, (2012) · Zbl 1244.05192  Zhang, Z F; Chen, X E; Li, J W; etal., 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.