×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total colorings of planar graphs. (English) Zbl 1325.05083
Summary: A total \([k]\)-coloring of a graph \(G\) is a mapping \(\phi : V (G) \cup E(G)\to [k]=\{1, 2, \dots, k\}\) such that any two adjacent or incident elements in \(V (G) \cup E(G)\) receive different colors. Let \(f(v)\) denote the sum of the color of a vertex \(v\) and the colors of all incident edges of \(v\). A total \([k]\)-neighbor sum distinguishing-coloring of \(G\) is a total \([k]\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(f(u)\neq f(v)\). By \(\chi ^{\prime\prime}_{nsd}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). M. Pilśniak and M. Woźniak [“On the adjacent-vertex-distinguishing index by sums in total proper colorings”, Preprint] conjectured \(\chi_{nsd}^{\prime\prime}(G)\leq \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that this conjecture holds for any planar graph with maximum degree at least 13.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy JA, Murty USR (1976) Graph theory with applications. North-Holland, New York
[2] Chen, X, On the adjacent vertex distinguishing total coloring numbers of graphs with \(Δ = 3\), Discret Math, 308, 4003-4007, (2008) · Zbl 1203.05052
[3] Ding L, Wang G, Yan G Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz (submitted) · Zbl 1303.05058
[4] Ding L, Wang, G Neighbor sum distinguishing total colorings via the combinatorial Nullstellensatz revisited (submitted) · Zbl 1303.05058
[5] Dong A, Wang G Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sin (to appear) · Zbl 1408.05061
[6] Huang, D; Wang, W, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci Sin Math, 42, 151-164, (2012)
[7] Hulgan, J, Concise proofs for adjacent vertex-distinguishing total colorings, Discret Math, 309, 2548-2550, (2009) · Zbl 1221.05143
[8] Huang, P; Wong, T; Zhu, X, Weighted-1-antimagic graphs of prime power order, Discret 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 Ser B, 100, 347-349, (2010) · Zbl 1209.05087
[10] Karoński, M; Łuczak, T; Thomason, A, Edge weights and vertex colours, J Comb Theory Ser B, 91, 151-157, (2004) · Zbl 1042.05045
[11] Li H, Liu B, Wang G (2013) Neighor sum distinguishing total colorings of \(K_4\)-minor free graphs. Front Math China. doi:10.1007/s11464-013-0322-x · Zbl 1042.05045
[12] Pilśniak M, Woźniak M (2011) On the adjacent-vertex-distinguishing index by sums in total proper colorings, Preprint MD 051. http://www.ii.uj.edu.pl/preMD/index.php · Zbl 1217.05202
[13] Przybyło, J, Irregularity strength of regular graphs, Electron J Comb, 15, r82, (2008) · Zbl 1163.05329
[14] Przybyło, J, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J Discret Math, 23, 511-516, (2009) · Zbl 1216.05135
[15] Przybyło, J; Woźniak, M, Total weight choosability of graphs, Electron J Combin, 18, p112, (2011) · Zbl 1217.05202
[16] Przybyło, J; Woźniak, M, On a 1,2 conjecture, Discret Math Theor Comput Sci, 12, 101-108, (2010) · Zbl 1250.05093
[17] Seamone B The 1-2-3 conjecture and related problems: a survey. arXiv:1211.5122
[18] Wang, H, On the adjacent vertex distinguishing total chromatic number of the graphs with \(Δ (G)=3\), J Comb Optim, 14, 87-109, (2007) · Zbl 1125.05043
[19] Wang W, Huang D (2012) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim. doi:10.1007/s10878-012-9527-2 · Zbl 1319.90076
[20] Wang, W; Wang, P, On adjacent-vertex- distinguishing total coloring of \(K_4\)-minor free graphs, Sci China Ser A Math, 39, 1462-1472, (2009)
[21] Wang, Y; Wang, W, Adjacent vertex distinguishing total colorings of outerplanar graphs, J Comb Optim, 19, 123-133, (2010) · Zbl 1216.05039
[22] Zhang, Z; Chen, X; Li, J; Yao, B; Lu, X; Wang, J, On adjacent-vertex-distinguishing total coloring of graphs, Sci China Ser A Math, 48, 289-299, (2005) · Zbl 1080.05036
[23] Wong, T; Zhu, X, Total weight choosability of graphs, J Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[24] Wong, T; Zhu, X, Antimagic labelling of vertex weighted graphs, J Graph Theory, 3, 348-350, (2012) · Zbl 1244.05192
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.