×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total colorings of triangle free planar graphs. (English) Zbl 1317.05065
Summary: A total \(k\)-coloring \(c\) of a graph \(G\) is a proper total coloring \(c\) of \(G\) using colors of the set \([k]=\{1,2,\dots ,k\}\). Let \(f(u)\) denote the sum of the color on a vertex \(u\) and colors on all the edges incident to \(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)\), \(f(u)\neq f(v)\). By \(\chi''_{\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)] conjectured that \(\chi''_{\mathrm{nsd}}(G)\leq \Delta (G)+3\) for any simple graph with maximum degree \(\Delta(G)\). In this paper, by using the famous Combinatorial Nullstellensatz, we prove that the conjecture holds for any triangle free planar graph with maximum degree at least 7.

MSC:
05C15 Coloring of graphs and hypergraphs
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. A., Murty, U. S. R.: Graph Theory with Applications, North-Holland, New York, 1976 · 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 Ser. A, 57, 1875-1882, (2014) · Zbl 1303.05058
[5] Ding, L., Wang, G., Wu, J., Yu, J.: 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., Engl. Series, 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] Karoński, M; Łuczak, T; Thomason, A, Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157, (2004) · Zbl 1042.05045
[10] Li, H., Ding, L., Liu, B., et al.: Neighbor sum distinguishing total colorings of planar graphs. J. Comb. Optim., DOI: 10.1007/s10878-013-9660-6 · Zbl 1325.05083
[11] 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
[12] Pilśniak, M., Woźniak, M.: On the total-neighbor-distinguishing index by sums. Graph and Combin., DOI 10.1007/s00373-013-1399-4 · Zbl 1303.05058
[13] Przybyło, J.: Irregularity strength of regular graphs. Electron. J. Combin., 15(1), #R82, 10pp (2008) · Zbl 1163.05329
[14] Przybyło, J, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23, 511-516, (2009) · Zbl 1216.05135
[15] Przybyło, J; Woźniak, M, On a 1, 2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 101-108, (2010) · Zbl 1250.05093
[16] Przybyło, J., Woźniak, M.: Total weight choosability of graphs. Electron. J. Combin., 18, #P112, 11pp (2011)
[17] Seamone, B.: The 1-2-3 conjecture and related problems: a survey, arXiv:1211.5122 · Zbl 1302.05059
[18] Wang, W., Huang, D.: The adjacent vertex distinguishing total coloring of planar graphs. J. Comb. Optim., DOI 10.1007/s10878-012-9527-2 · Zbl 1319.90076
[19] Wang, W; Wang, P, On adjacent-vertex-distinguishing total coloring of \(K\)_{4}-minor free graphs, Sci. China, Ser. A, 39, 1462-1472, (2009)
[20] Kalkowski, M; Karoński, M; Pfender, F, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory Ser. B, 100, 347-349, (2010) · Zbl 1209.05087
[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; etal., 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.