×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of planar graphs without 5-cycles. (English) Zbl 1372.05072
Summary: Let \(G\) be a graph, a proper total coloring \(\phi : V(G) \cup E(G) \rightarrow \{1, 2, \ldots, k \}\) is called neighbor sum distinguishing if \(f(u) \neq f(v)\) for each edge \(uv\in E(G)\), where \(f(v) = \sum_{uv \in E(G)} \phi(uv) + \phi(v)\), \(v \in V(G)\). We use \(\chi_{\Sigma}^{\prime \prime}(G)\) to denote the smallest number \(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] have already conjectured that \(\chi_{\Sigma}^{\prime \prime}(G) \leq \Delta(G) + 3\) for any simple graph with maximum degree \(\Delta(G)\). In this paper, we prove that for any planar graph \(G\) without 5-cycles, \(\chi_{\Sigma}^{\prime \prime}(G)\leq \max \{\Delta(G) + 3, 10\}\).

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., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026
[2] Bondy, J.; Murty, U., Graph theory with applications, (1976), North-Holland New York · Zbl 1226.05083
[3] L. Ding, G. Wang, J. Wu, J. Yu, Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, submitted for publication. · Zbl 1371.05078
[4] 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
[5] Gong, X.; Xu, C.; Song, H.; Pan, W., Neighbor sum distinguishing total coloring of a kind of sparse graph, Ars Combin., 127, 133-141, (2016) · Zbl 1413.05111
[6] 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
[7] 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
[8] Pilśniak, M.; Woźniak, M., On the adjacent-vertex-distinguishing index by sums in total proper colorings, Preprint MD 051
[9] Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 609, 162-170, (2015) · Zbl 1331.05084
[10] Song, H.; Pan, W.; Gong, X.; Xu, C., A note on the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 640, 125-129, (2016) · Zbl 1345.05035
[11] 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
[12] Wang, G.; Ding, L.; Cheng, X.; Wu, J., Improved bounds for neighbor sum (set) distinguishing choosability of planar graphs, SIAM Discrete Math., (2017), submitted for publication
[13] Wang, J.; Ma, Q.; Han, X., Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sin. (Engl. Ser.), 31, 2, 216-224, (2015) · Zbl 1317.05065
[14] Yao, J.; Kong, H., Neighbor sum distinguishing total choosability of graphs with large maximum average degree, Ars Combin., 125, 347-360, (2016) · Zbl 1413.05353
[15] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum distinguishing total coloring of 2-degenerate graphs, J. Comb. Optim., 34, 64-70, (2017) · Zbl 1394.05037
[16] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum (set) distinguishing total choosability of d-degenerate graphs, Graphs Combin., 32, 1611-1620, (2016) · Zbl 1342.05052
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.