×

zbMATH — the first resource for mathematics

A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles. (English) Zbl 1343.05066
Summary: Let \(G=(V,E)\) be a graph and \(\phi\) be a total \(k\)-coloring of \(G\) using the color set \(\{1,\dots,k\}\). Let \(\sum_\phi(u)\) denote the sum of the color of the vertex \(u\) and the colors of all incident edges of \(u\). A \(k\)-neighbor sum distinguishing total coloring of \(G\) is a total \(k\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(\sum_\phi(u)\neq\sum_\phi(v)\). By \(\chi^{\prime\prime}_{\mathrm{nsd}}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] first introduced this coloring and conjectured that \(\chi^{\prime\prime}_{\mathrm{nsd}}(G)\leq\Delta (G)+3\) for any simple graph \(G\). In this paper, we prove that the conjecture holds for planar graphs without intersecting triangles with \(\Delta (G)\geq 7\). Moreover, we also show that \(\chi^{\prime\prime}_{\mathrm{nsd}}(G)\leq\Delta (G)+2\) for planar graphs without intersecting triangles with \(\Delta (G)\geq 9\). Our approach is based on the Combinatorial Nullstellensatz and the discharging method.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N, No article title, Combinatorial Nullstellensatz. Comb Probab. Comput, 8, 7-29, (1999) · Zbl 0920.05026
[2] Bondy JA, Murty USR (1976) Graph theory with applications. North-Holland, New York · Zbl 1226.05083
[3] Chen, X, On the adjacent vertex distinguishing total coloring numbers of graphs with \(Δ = 3\), Discrete Math, 308, 4003-4007, (2008) · Zbl 1203.05052
[4] Ding, L; Wang, G; Yan, G, Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci China Math, 57, 1875-1882, (2013) · Zbl 1303.05058
[5] Ding L, Wang G, Wu J, Yu J (2014) Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, submitted · Zbl 1371.05078
[6] Dong, A; Wang, G, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math Sin, 30, 703-709, (2014) · Zbl 1408.05061
[7] Huang, D; Wang, W, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, (in Chinese), Sci Sin Math, 42, 151-164, (2012)
[8] Huang, P; Wong, T; Zhu, X, Weighted-1-antimagic graphs of prime power order, Discrete Math, 312, 2162-2169, (2012) · Zbl 1244.05186
[9] Kalkowski, M; Karoński, M; Pfender, F, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J Comb Theory, 100, 347-349, (2010) · Zbl 1209.05087
[10] 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
[11] Li, H; Ding, L; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of planar graphs, J Comb Optim, (2013) · Zbl 1325.05083
[12] Pilśniak, M; Woźniak, M, On the total-neighbor-distinguishing index by sums, Graph Comb, (2013) · Zbl 1312.05054
[13] Przybyło, J, Irregularity strength of regular graphs, Electron J Comb, 15, 1, (2008) · Zbl 1163.05329
[14] Przybyło, J; Woźniak, M, Total weight choosability of graphs, Electron J Comb, 18, p112, (2011) · Zbl 1217.05202
[15] Seamone B (2012) The 1-2-3 conjecture and related problems: a survey. arXiv:1211.5122 · Zbl 1297.05093
[16] Wang, W; Wang, P, On adjacent-vertex- distinguishing total coloring of \(K_4\)-minor free graphs, Sci China, 39, 1462-1472, (2009)
[17] Wang, W; Huang, D, The adjacent vertex distinguishing total coloring of planar graphs, J Comb Opt, (2012) · Zbl 1319.90076
[18] Wang, GH; Yan, GY, An improved upper bound for the neighbor sum distinguishing index of graphs, Discrete Appl Math, 175, 126-128, (2014) · Zbl 1297.05093
[19] Wang, GH; Chen, ZM; Wang, JH, Neighbor sum distinguishing index of planar graphs, Discrete Math, 334, 70-73, (2014) · Zbl 1298.05136
[20] Wang, J; Ma, Q; Han, X, Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math Sin, 31, 216-224, (2015) · Zbl 1317.05065
[21] Wong, T; Zhu, X, Total weight choosability of graphs, J Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[22] Wong, T; Zhu, X, Antimagic labelling of vertex weighted graphs, J Graph Theory, 3, 348-359, (2012) · Zbl 1244.05192
[23] Zhang, Z; Chen, X; Li, J; Yao, B; Lu, X; Wang, J, On adjacent-vertex- distinguishing total coloring of graphs, Sci China, 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.