×

zbMATH — the first resource for mathematics

Neighbor distinguishing total choice number of sparse graphs via the combinatorial nullstellensatz. (English) Zbl 1336.05046
Summary: Let \(G=(V,E)\) be a graph and \(\phi:V\cup E\to\{1,2,\dots, k\}\) be a total-\(k\)-coloring of \(G\). Let \(f(v)(S(v))\) denote the sum(set) of the color of vertex \(v\) and the colors of the edges incident with \(v\). The total coloring \(\phi\) is called neighbor sum distinguishing if \((f(u)\neq f(v))\) for each edge \(uv\in E(G)\). We say that \(\phi\) is neighbor set distinguishing or adjacent vertex distinguishing if \(S(u)\neq S(v)\) for each edge \(uv\in E(G)\). For both problems, we have conjectures that such colorings exist for any graph \(G\) if \(k\geq \Delta(G)+3\). The maximum average degree of \(G\) is the maximum of the average degree of its non-empty subgraphs, which is denoted by \(\mathrm{mad}(G)\). In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that these two conjectures hold for sparse graphs in their list versions. More precisely, we prove that every graph \(G\) with maximum degree \(\Delta (G)\) and maximum average degree \(\mathrm{mad}(G)\) has \(ch_\Sigma^{\prime\prime}(G)\leq \Delta(G)+3\) (where \(ch_\Sigma^{\prime\prime}(G)\) is the neighbor sum distinguishing total choice number of \(G\)) if there exists a pair \((k,m)\in \{ (6,4),(5,\frac{18}{5}),(4,\frac{16}{5})\}\) such that \(\Delta(G)\geq k\) and \(\mathrm{mad}(G)<m\).

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. North-Holland, New York, 1976 · Zbl 1226.05083
[3] Chartrand, G.; Jacobson, M.; Lehel, J.; Oellermann, O.; Ruiz, S.; Saba, F., Irregular networks, Congr. Numer., 64, 197-210, (1988) · Zbl 0671.05060
[4] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with δ = 3, Discrete Math., 17, 4003-4007, (2008) · Zbl 1203.05052
[5] Ding, L.; Wang, G.; Yan, G., Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. Sin. Math., 57, 1875-1882, (2014) · Zbl 1303.05058
[6] Ding, L., Wang, G., Wu, J., Yu, J. Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz. Graphs and Combin., submitted. (2014) · Zbl 1371.05078
[7] 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
[8] Huang, D.; Wang, W., Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci. Sin. Math., 42, 151-164, (2012)
[9] Huang, P.; Wong, T.; Zhu, X., Weighted-1-antimagic graphs of prime power order, Discrete Math., 312, 2162-2169, (2012) · Zbl 1244.05186
[10] Kalkowski, M.; Karónski, 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
[11] Karónski, M.; Luczak, T.; Thomason, A., Edge weights and vertex colors, J. Combin. Theory Ser. B, 91, 151-157, (2004) · Zbl 1042.05045
[12] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 1-14, (2013)
[13] 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
[14] Pilsniak, M.; Wózniak, M., On the total-neighbor-distinguishing index by sums, Graphs and Combin., 31, 771-782, (2015) · Zbl 1312.05054
[15] Przybylo, J., Irregularity strength of regular graphs, Electronic J. Combin., 15, r82, (2008) · Zbl 1163.05329
[16] Przybylo, 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
[17] Przybylo, J., Neighbour distinguishing edge colorings via the combinatorial nullstellensatz, SIAM J. Discrete Math., 27, 1313-1322, (2013) · Zbl 1290.05079
[18] Przybylo, J.; Wózniak, M., Total weight choosability of graphs, Electronic J. Combin., 18, p112, (2011) · Zbl 1217.05202
[19] Przybylo, J.; Wózniak, M., On a 1,2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 101-108, (2010) · Zbl 1250.05093
[20] Seamone, B. The 1-2-3 conjecture and related problems: a survey. ArXiv: 1211.5122 (2012)
[21] Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, J. Combin. Optim., 27, 379-396, (2014) · Zbl 1319.90076
[22] Wang, W.; Wang, P., On adjacent-vertex-distinguishing total coloring of K4-minor free graphs, Sci. China Ser. A, 39, 1462-1472, (2009)
[23] Wang, Y.; Wang, W., Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Comb. Optim., 19, 123-133, (2010) · Zbl 1216.05039
[24] Wong, T.; Zhu, X., Total weight choosability of graphs, J. Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[25] Wong, T.; Zhu, X., Antimagic labelling of vertex weighted graphs, J. Graph Theory, 70, 348-359, (2012) · Zbl 1244.05192
[26] 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.