×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of 2-degenerate graphs. (English) Zbl 1394.05037
A proper \(k\)-total coloring of a graph \(G\) is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\dots,k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let \(f(v)\) denote the sum of the colors on the edges incident with \(v\) and the color on vertex \(v\). A proper \(k\)-total coloring of \(G\) is called neighbor sum distinguishing if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). The smallest number \(k\) in the neighbor sum distinguishing \(k\)-total coloring of \(G\) is the neighbor sum distinguishing total chromatic number. M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] conjectured that for any graph G the neighbor sum distinguishing total chromatic number is at most \(\Delta(G)+3\). In this paper, the authors confirm this conjecture for 2-degenerate graphs. Moreover, they improve this bound for graphs with maximum degree at least 5. They prove that if \(G\) is 2-degenerate with \(\Delta(G)\geq 5\) then the neighbor sum distinguishing total chromatic number is at most \(\Delta(G)+2\). The proof is based on the combinatorial Nullstellensatz. Recently, L. Ding et al. [ibid. 33, No. 4, 885–900 (2017; Zbl 1371.05078)] proved that if \(G\) is not a forest and \(\Delta(G)\geq 4\) then the neighbor sum distinguishing total chromatic number of \(G\) is at most \(\Delta (G)+2\mathrm{col}(G)-1\), where col\((G)\) is the coloring number of \(G\), in particular, the neighbor sum distinguishing total chromatic number of 2-degenerate graph \(G\) with \(\Delta(G)\geq 4\) is at most \(\Delta(G)+3\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N, Combinatorial nullstellensatz, Comb Probab Comput, 8, 7-29, (1999) · Zbl 0920.05026
[2] Bondy J, Murty U (2008) Graph theory. Springer, London · Zbl 1134.05001
[3] Ding L, Wang G, Wu J, Yu J (2015) Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Subimitted · Zbl 1371.05078
[4] 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
[5] Dong, A; Wang, G, Neighbor sum distinguishing total coloring of graphs with bounded maximum average degree, Acta Math Sin, 30, 703-709, (2014) · Zbl 1408.05061
[6] Li, H; Ding, L; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of planar graphs, J Comb Optim, 30, 675-688, (2015) · Zbl 1325.05083
[7] Li, H; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of \(K_{4}\)-minor free graphs, Front Math China, 8, 1351-1366, (2013) · Zbl 1306.05066
[8] Pilśniak M, Woźniak M (2013) On the adjacent vertex disinguishing index by sums in total proper colorings. Graphs Comb. doi:10.1007/s00373-013-1399-4
[9] Qu, C; Wang, G; Wu, J; Yu, X, On the neighbor sum distinguishing total coloring of planar graphs, Theor Comp Sci, 609, 162-170, (2016) · Zbl 1331.05084
[10] Wang, Y; Chen, J; Luo, R; Mulley, G, Adjacent vertex distinguishing edge coloring of 2-degenerate graphs, J Comb Optim, 31, 874-880, (2016) · Zbl 1342.90215
[11] Wang W, Huang D (2014) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim 27(2):379-396 · Zbl 1319.90076
[12] Wang, W; Wang, P, On adjacent-vertex-distinguishing total coloring of \(K_{4}\)-minor free graphs, Sci China Ser A, 39, 1462-1472, (2009)
[13] Yao J, Yu X, Wang G, Xu C (2016) Neighbor sum (set) distinguishing total choosability of \(d\)-degenerate graphs. Graphs Comb 32(4):1611-1620 · Zbl 1342.05052
[14] 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.