×

zbMATH — the first resource for mathematics

Neighbor sum (set) distinguishing total choosability of \(d\)-degenerate graphs. (English) Zbl 1342.05052
Summary: Let \(G=(V,E)\) be a graph with maximum degree \(\varDelta (G)\) and \(\phi:V\cup E\to\{1,2,\dots,k\}\) be a proper total coloring of the graph \(G\). Let \(S(v)\) denote the set of the color on vertex \(v\) and the colors on the edges incident with \(v\). Let \(f(v)\) denote the sum of the color on vertex \(v\) and the colors on the edges incident with \(v\). The proper total coloring \(\phi\) is called neighbor set distinguishing or adjacent vertex distinguishing if \(S(u)\neq S(v)\) for each edge \(uv\in E(G)\). We say that \(\phi\) is neighbor sum distinguishing if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). In both problems the challenging conjectures presume that such colorings exist for any graph \(G\) if \(k\geq\varDelta (G)+3\). Ding et al. proved in both problems \(k\geq\varDelta (G)+2d\) is sufficient for \(d\)-degenerate graph \(G\). In this paper, we improve this bound and prove that \(k\geq\varDelta (G)+d+1\) is sufficient for \(d\)-degenerate graph \(G\) with \(d\leq 8\) and \(\varDelta (G)\geq 2d\) or \(d\geq 9\) and \(\varDelta (G)\geq\frac{5}{2}d-5\). In fact, we prove these results in their list versions. As a consequence, we obtain an upper bound of the form \(\varDelta (G)+C\) for some families of graphs, e.g. \(\varDelta (G)+6\) for planar graphs with \(\varDelta (G)\geq 10\). In particular, we therefore obtain that when \(\varDelta (G)\geq 4\) two conjectures we mentioned above hold for 2-degenerate graphs in their list versions.

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.: Graph theory. Springer, London (2008) · Zbl 1134.05001
[3] Chen, X, On the adjacent vertex distinguishing total coloring numbers of graphs with \(\varDelta =3\), Discrete Math., 308, 4003-4007, (2008) · Zbl 1203.05052
[4] Cheng, X; Wu, J; Huang, D; Wang, G, Neighbor sum distinguishing total colorings of planar with maximum degree \(\varDelta \), Discret. Appl. Math., 190, 34-41, (2015) · Zbl 1316.05041
[5] Ding, L., Wang, G., Wu, J., Yu, J.: Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz. Sci. China. Math. 57(9), 1875-1882 · Zbl 1303.05058
[6] 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
[7] 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
[8] Li, H; Ding, L; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 675-685, (2015) · Zbl 1325.05083
[9] 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
[10] Przybyło, J, Neighbor distinguishing edge colorings via combinatorial nullstellensatz, SIAM J. Discrete Math., 27, 1313-1322, (2013) · Zbl 1290.05079
[11] Pilśniak, M., Woźniak, M.: On the adjacent vertex distinguishing index by sums in total proper colorings. Graphs Comb. (2013). doi:10.1007/s00373-013-1399-4
[12] Wang, G., Ding, L., Cheng X., Wu, J.: Improved bounds for neighbor sum (set) distinguishing choosability of planar graphs, Submitted
[13] Wang, W; Huang, D, The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim., 27, 379-396, (2014) · Zbl 1319.90076
[14] Wang, W; Wang, P, On adjacent-vertex-distinguishing total coloring of \(K_{4}\)-minor free graphs, Sci. China Ser. A, 39, 1462-1472, (2009)
[15] Wang, Y; Wang, W, Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Comb. Optim., 19, 123-133, (2010) · Zbl 1216.05039
[16] Yao, J., Yu, X., Wang, G., Xu, C.: Neighbor sum distinguishing total coloring of 2-degenerate graph, Submitted · Zbl 1394.05037
[17] 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.