×

Neighbor sum distinguishing total choosability of 1-planar graphs with maximum degree at least 24. (English) Zbl 1455.05018

Summary: For a simple graph \(G\), a neighbor sum distinguishing total \(k\)-coloring of \(G\) is a mapping \(\phi \): \( V (G) \cup E (G) \to \{1, 2, \ldots, k\}\) such that no two adjacent or incident elements in \(V (G) \cup E (G)\) receive the same color and \(w_\phi (u) \neq w_\phi (v)\) for each edge \(u v \in E (G)\), where \(w_\phi (v)\) (or \(w_\phi (u))\) denotes the sum of the color of \(v\) (or \(u)\) and the colors of all edges incident with \(v\) (or \(u)\). For each element \(x \in V (G) \cup E (G)\), let \(L(x)\) be a list of integer numbers. If, whenever we give a list assignment \(L = \{L (x) \mid | L (x) | = k, x \in V (G) \cup E (G)\}\), there exists a neighbor sum distinguishing total \(k\)-coloring \(\phi\) such that \(\phi (x) \in L (x)\) for each element \(x \in V (G) \cup E (G)\), then we say that \(\phi\) is a list neighbor sum distinguishing total \(k\)-coloring. The smallest \(k\) for which such a coloring exists is called the neighbor sum distinguishing total choosability of \(G\), denoted by \(\operatorname{ch}_{\Sigma}^{\prime\prime} (G)\). A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. There is almost no result yet about \(\operatorname{ch}_{\Sigma}^{\prime\prime} (G)\) if \(G\) is a 1-planar graph. We prove that \(\operatorname{ch}_{\Sigma}^{\prime\prime} (G) \leq \Delta + 3\) for every 1-planar graph \(G\) with maximum degree \(\Delta \geq 24\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29 (1999) · Zbl 0920.05026
[2] Bartnicki, T.; Bosek, B.; Czerwiński, S., Additive coloring of planar graphs, Graphs Combin., 30, 1087-1098 (2014) · Zbl 1298.05102
[3] Bondy, J.; Murty, U., Graph Theory with Applications (1976), North-Holland: North-Holland New York · Zbl 1226.05083
[4] Ding, L. H.; Wang, G. H.; Wu, J. L.; Yu, J. G., Neighbor sum (set) distinguishing total choosability via the combinatorial nullstellensatz, Graphs Combin., 33, 4, 885-900 (2017) · Zbl 1371.05078
[5] Ding, L. H.; Wang, G. H.; Yan, G. Y., Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. China Ser. A, 57, 9, 1875-1882 (2013) · Zbl 1303.05058
[6] Dong, A. J.; Wang, G. H., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin. (Engl. Ser.), 30, 4, 703-709 (2014) · Zbl 1408.05061
[7] Flandrin, E.; Marczyk, A.; Przybyło, J.; Saclé, J. F.; Woźniak, M., Neighbor sum distinguishing index, Graphs Combin., 29, 1329-1336 (2013) · Zbl 1272.05047
[8] Huang, P.; Wong, T.; Zhu, X., Weighted-1-antimagic graphs of prime power order, Discrete Math., 312, 14, 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. Combin. Theory Ser. B, 100, 347-349 (2010) · Zbl 1209.05087
[10] Karoski, M.; Luczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157 (2004) · Zbl 1042.05045
[11] Li, H. L.; Liu, B. Q.; Wang, G. H., Neighor sum distinguishing total colorings of \(K_4\)-minor free graphs, Front. Math. China, 8, 6, 1351-1366 (2013) · Zbl 1306.05066
[12] Loeb, S.; Przybyło, J.; Tang, Y., Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discrete Math., 340, 2, 58-62 (2017) · Zbl 1351.05083
[13] Lu, Y.; Han, M. M.; Luo, R., Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring, Discrete Appl. Math., 237, 109-115 (2018) · Zbl 1380.05076
[14] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782 (2015) · Zbl 1312.05054
[15] Przybyło, J., Irregularity strength of regular graphs, Electron. J. Combin., 15, 1, 82 (2008) · Zbl 1163.05329
[16] Przybyło, J.; Woźniak, M., Total weight choosability of graphs, Electron. J. Combin., 18, 112 (2011) · Zbl 1217.05202
[17] Qu, C. Q.; Wang, G. H.; Yan, G. Y.; Yu, X. W., Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim., 32, 3, 906-916 (2016) · Zbl 1348.05082
[18] Ringel, G., Ein sechsfarbenproblem auf der kugel, Abh. Math. Semin. Univ. Hambg., 29, 107-117 (1965) · Zbl 0132.20701
[19] Seamone, B., The 1-2-3 conjecture and related problems: a survey (2012), arXiv:1211.5122
[20] Song, W. Y.; Miao, L. Y.; Li, J. B.; Zhao, Y. Y.; Pang, J. R., Neighbor sum distinguishing total coloring of sparse IC-planar graphs, Discrete Appl. Math., 239, 183-192 (2018) · Zbl 1382.05019
[21] Wang, J. H.; Cai, J. S.; Liu, B. J., Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, Theoret. Comput. Sci., 661, 1-7 (2017) · Zbl 1357.05027
[22] Wang, J. H.; Cai, J. S.; Ma, Q. L., Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Appl. Math., 206, 215-219 (2016) · Zbl 1335.05051
[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, 70, 348-359 (2012) · Zbl 1244.05192
[25] Yang, D. L.; Sun, L.; Yu, X. W.; Wu, J. L.; Zhou, S., Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree \(10\), Appl. Math. Comput., 314, 456-468 (2017) · Zbl 1426.05051
[26] Zhang, Z.; Cheng, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A, 48, 3, 289-299 (2005) · Zbl 1080.05036
[27] Zhang, X.; Wu, J. L., On edge colorings of 1-planar graphs, Inform. Process. Lett., 111, 124-128 (2011) · Zbl 1259.05050
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.