×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles. (English) Zbl 1357.05027
Summary: A total \(k\)-coloring of \(G\) is a mapping \(\phi : V(G) \cup E(G) \rightarrow \{1, \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 colors of the edges incident to \(v\) and the color of \(v\). A \(k\)-neighbor sum distinguishing total coloring of \(G\) is a total \(k\)-coloring of \(G\) such that for each edge \(u v \in E(G)\), \(f(u) \neq f(v)\). By \(\chi_\Sigma^{\prime \prime}(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_\Sigma^{\prime \prime}(G) \leq \operatorname{\Delta}(G) + 3\) for any simple graph \(G\). Let \(L_z\) \((z \in V \cup E)\) be a set of lists of integer numbers, each of size \(k\). The smallest \(k\) for which for any specified collection of such lists, there exists a neighbor sum distinguishing total coloring using colors from \(L_z\) for each \(z \in V \cup E\) is called the neighbor sum distinguishing total choosability of \(G\), and denoted by \(\mathrm{ch}_\Sigma^{\prime \prime}(G)\). In this paper, we prove that \(\mathrm{ch}_\Sigma^{\prime \prime}(G) \leq \operatorname{\Delta}(G) + 3\) for planar graphs without adjacent triangles with \(\operatorname{\Delta}(G) \geq 8\), which implies that the conjecture proposed by M. Pilśniak and M. Woźniak [loc. cit.] is true for these planar graphs.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, J. A.; Murty, U. S.R., Graph theory with applications, (1976), North-Holland New York · Zbl 1134.05001
[2] 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, 3, 289-299, (2005) · Zbl 1080.05036
[3] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with \(\operatorname{\Delta} = 3\), Discrete Math., 308, 17, 4003-4007, (2008) · Zbl 1203.05052
[4] Huang, D.; Wang, W., Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci. Sin. Math., 42, 2, 151-164, (2012), (in Chinese)
[5] Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim., 27, 2, 379-396, (2014) · Zbl 1319.90076
[6] Wang, W.; Wang, P., On adjacent-vertex-distinguishing total coloring of \(K_4\)-minor free graphs, Sci. China Ser. A Math., 39, 12, 1462-1472, (2009)
[7] Wang, Y.; Wang, W., Adjacent vertex distinguishing total coloring of outerplanar graphs, J. Comb. Optim., 19, 123-133, (2010) · Zbl 1216.05039
[8] Seamone, B., The 1-2-3 conjecture and related problems: a survey
[9] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782, (2015) · Zbl 1312.05054
[10] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin., 30, 4, 703-709, (2014) · Zbl 1408.05061
[11] Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs, Front. Math. China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066
[12] Ding, L.; Wang, G.; Yan, G., Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. China Math., 57, 9, 1875-1882, (2014) · Zbl 1303.05058
[13] L. Ding, G. Wang, J. Wu, J. Yu, Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, submitted for publication. · Zbl 1371.05078
[14] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688, (2015) · Zbl 1325.05083
[15] Miao, Z.; Rui, S.; Hu, X.; Luo, R., Adjacent vertex distinguishing total colorings of 2-degenerate graphs, Discrete Math., 339, 10, 2446-2449, (2016) · Zbl 1339.05141
[16] Wang, J.; Ma, Q.; Han, X.; Wang, X., A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles, J. Comb. Optim., 32, 2, 626-638, (2016) · Zbl 1343.05066
[17] Wang, J.; Cai, J.; Ma, Q., Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Appl. Math., 206, 215-219, (2016) · Zbl 1335.05051
[18] Qu, C.; Wang, G.; Yan, G.; Yu, X., Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim., 32, 3, 906-916, (2016) · Zbl 1348.05082
[19] Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 609, 1, 162-170, (2016) · Zbl 1331.05084
[20] Alon, N., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026
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.