×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring. (English) Zbl 1380.05076
Summary: Let \(\chi_\varSigma^t(G)\) and \(\chi_\varSigma^{l t}(G)\) be the neighbor sum distinguishing total chromatic and total choice numbers of a graph \(G\), respectively. In this paper, we present some new upper bounds of \(\chi_\varSigma^{l t}(G)\) for \(\ell\)-degenerate graphs with integer \(\ell \geq 1\), and of \(\chi_\varSigma^t(G)\) for 2-degenerate graphs. As applications of these results, (i) for a general graph \(G\), \(\chi_\varSigma^t(G) \leq \chi_\varSigma^{l t}(G) \leq \max \{\varDelta(G) + \lfloor \frac{3 \operatorname{col}(G)}{2} \rfloor - 1, 3 \operatorname{col}(G) - 2 \}\), where \(\operatorname{col}(G)\) is the coloring number of \(G\); (ii) for a 2-degenerate graph \(G\), we determine the exact value of \(\chi_\varSigma^t(G)\) if \(\varDelta(G) \geq 6\) and show that \(\chi_\varSigma^t(G) \leq 7\) if \(\varDelta(G) \leq 5\).

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] Bartnicki, T.; Grytczuk, J.; Niwczyk, S., Weight choosability of graphs, J. Graph Theory, 60, 3, 242-256, (2009) · Zbl 1210.05138
[3] Bondy, J. A.; Murty, U. S.R., Graph theory, (GTM, Vol. 244, (2008), Springer) · Zbl 1134.05001
[4] Chang, G. J.; Narayanan, N., Strong chromatic index of 2-degenerate graphs, J. Graph Theory, 73, 2, 119-126, (2013) · Zbl 1264.05047
[5] Ding, L. H.; Wang, G. H.; Yan, G. Y., Neighbor sum distinguishing total coloring via the combinatorial nullstellensatz, sin, China Ser. Math, 57, 9, 1875-1882, (2014) · Zbl 1303.05058
[6] Dong, A. J.; Wang, G. H., Neighbor sum distinguishing total coloring of graphs with bounded maximum average degree, Acta Math. Sinica, Engl. Ser. Mar., 30, 4, 703-709, (2014) · Zbl 1408.05061
[7] Dong, A. J.; Wang, G. H.; Zhang, J. H., Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree, Discrete Appl. Math., 166, 84-90, (2014) · Zbl 1283.05090
[8] Flandrin, E.; Marczyk, A.; Przybyło, J.; Saclé, J.-F.; Woźniak, M., Neighbor sum distinguishing index, Graphs Combin., 29, 1329-1336, (2013) · Zbl 1272.05047
[9] Hu, X. L.; Chen, Y. J.; Luo, R.; Miao, Z. K., Neighbor sum distinguishing index of 2-degenerate graphs, J. Comb. Optim., 34, 3, 798-809, (2017) · Zbl 1376.05056
[10] M. Kalkowski, A note on 1,2-Conjecture, in Ph.D Thesis, 2009.
[11] 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
[12] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 1, 151-157, (2004) · Zbl 1042.05045
[13] Li, H. L.; Ding, L. H.; Liu, B. Q.; Wang, G. H., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688, (2015) · Zbl 1325.05083
[14] Li, H. L.; Liu, B. Q.; Wang, G. H., Neighbor sum distinguishing total coloring of \(K_4\)-minor-free graphs, Front. Math. China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066
[15] Pilśniak, M.; Woźniak, M., On the total-neighbor distinguishing index by sums, Graphs Combin., 31, 3, 771-782, (2015) · Zbl 1312.05054
[16] Przybyło, J., A note on neighbor-distinguishing regular graphs total-weighting, Electron. J. Comb., 15, 1, (2008), #N 35 · Zbl 1159.05046
[17] Przybyło, J., Neighbor distinguishing edge colorings via the combinatorial nullstellensatz, SIAM J. Discrete Math., 27, 3, 1313-1322, (2013) · Zbl 1290.05079
[18] Przybyło, J.; Woźniak, M., On a 1,2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 1, 101-108, (2010) · Zbl 1250.05093
[19] Przybyło, J.; Woźniak, M., Total weight choosability of graphs, Electron. J. Combin., 18, #P112, (2011) · Zbl 1217.05202
[20] B. Seamone, The 1-2-3 Conjecture and related problems: a survey, arXiv:1211.5122v1. · Zbl 1302.05059
[21] Wang, G. H.; Chen, Z. M.; Wang, J. H., Neighbor sum distinguishing index of planar graphs, Discrete Math., 334, 70-73, (2014) · Zbl 1298.05136
[22] Wong, T.; Zhu, X., Total weight choosability, J. Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[23] Wong, T.; Zhu, X., Every graph is \((2, 3)\)-choosable, Combinatoria, 36, 1, 121-127, (2016) · Zbl 1374.05106
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.