×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N, Combinatorial nullstellensatz, Combin Probab Comput, 8, 7-29, (1999) · Zbl 0920.05026
[2] Bondy J A, Murty U S R. Graph Theory with Applications. New York: North-Holland, 1976 · Zbl 1226.05083
[3] Chen, X E, On the adjacent vertex distinguishing total coloring numbers of graphs with δ = 3, Discrete Math, 308, 4003-4007, (2008) · Zbl 1203.05052
[4] Cheng X H, Wu J L, Huang D J, et al. Neighbor sum distinguishing total colorings of planar graphs with maximum degree Δ. Submitted, 2013
[5] Dong, A J; Wang, G H, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, (2013)
[6] 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)
[7] 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
[8] 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
[9] Karoński, M; Łuczak, T; Thomason, A, Edge weights and vertex colors, J Combin Theory Ser B, 91, 151-157, (2004) · Zbl 1042.05045
[10] Li, H L; Ding, L H; Liu, B Q; etal., Neighbor sum distinguishing total colorings of planar graphs, (2013)
[11] 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
[12] 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
[13] Przybyło, J, Irregularity strength of regular graphs, Electronic J Combin, 15, #r82, (2008) · Zbl 1163.05329
[14] 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
[15] Przybyło, J, Neighbour distinguishing edge colorings via the combinatorial nullstellensatz, SIAM J Discrete Math, 27, 1313-1322, (2013) · Zbl 1290.05079
[16] Przybyło, J; Woźniak, M, Total weight choosability of graphs, Electronic J Combin, 18, #p112, (2011) · Zbl 1217.05202
[17] Przybyło, J; Woźniak, M, On a 1, 2 conjecture, Discrete Math Theor Comput Sci, 12, 101-108, (2010) · Zbl 1250.05093
[18] 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
[19] Seamone B. The 1-2-3 conjecture and related problems: A survey. ArXiv:1211.5122, 2012
[20] Wang, W F; Huang, D J, The adjacent vertex distinguishing total coloring of planar graphs, (2012)
[21] 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)
[22] Wang, Y Q; Wang, W F, Adjacent vertex distinguishing total colorings of outerplanar graphs, J Combin Optim, 19, 123-133, (2010) · Zbl 1216.05039
[23] Wong, T L; Zhu, X D, Total weight choosability of graphs, J Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[24] Wong, T L; Zhu, X D, Antimagic labelling of vertex weighted graphs, J Graph Theory, 3, 348-359, (2012) · Zbl 1244.05192
[25] 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.