×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of sparse IC-planar graphs. (English) Zbl 1382.05019
Summary: Two distinct crossings are independent if the end-vertices of the crossed edge are mutually different. If a graph \(G\) has a drawing in the plane such that every two crossings are independent, then we call \(G\) a plane graph with independent crossings or IC-planar graph for short. A proper total-\(k\)-coloring of a graph \(G\) is a mapping \(c : V(G) \cup E(G)\)\(\rightarrow \{1, 2,\ldots, k \}\) such that any two adjacent elements in \(V(G) \cup E(G)\) receive different colors. Let \(\sum_c(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 \(u v \in E(G)\), \(\sum_c(u) \neq \sum_c(v)\). The least number \(k\) needed for such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number, denoted by \(\chi_\Sigma^{\prime \prime}(G)\). In this paper, it is proved that \(\chi_\Sigma^{\prime \prime}(G) \leq \max \{\Delta(G) + 3, 11 \}\) if \(G\) is a triangle-free IC-planar graph, and \(\chi_\Sigma^{\prime \prime}(G) \leq \max \{\Delta(G) + 3, 15 \}\) if \(G\) is an IC-planar graph without adjacent triangles, where \(\Delta(G)\) is the maximum degree of \(G\).

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C42 Density (toughness, etc.)
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alberson, M. O., Chromatic number, independent ratio, and crossing number, Ars Math. Contemp., 1, 1-6, (2008) · Zbl 1181.05032
[2] Alon, N., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications, (1976), North-Holland New York · Zbl 1226.05083
[4] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta = 3\), Discrete Math., 308, 17, 4003-4007, (2008) · Zbl 1203.05052
[5] Cheng, X.; Huang, D.; Wang, G.; Wu, J., Neighbor sum distinguishing total colorings of planar graphs with maximum degree \(\Delta\), Discrete Appl. Math., 190, 34-41, (2015) · Zbl 1316.05041
[6] Coker, T.; Johannson, K., The adjacent vertex distinguishing total chromatic number, Discrete Math., 312, 741-750, (2012) · Zbl 1245.05042
[7] Ding, L.; Wang, G.; Wu, J.; Yu, J., Neighbor sum (set) distinguishing total choosability via the combinatorial nullstellensatz, Graphs Combin., 33, 4, 885-900, (2017) · Zbl 1371.05078
[8] Ding, L.; Wang, G.; Yan, G., Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. Sin. Math., 57, 9, 1875-1882, (2014) · Zbl 1303.05058
[9] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sinica, 30, 4, 703-709, (2014) · Zbl 1408.05061
[10] 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
[11] Huang, D.; Wang, W.; Yan, C., A note on the adjacent vertex distinguishing total chromatic number of graphs, Discrete Math., 312, 24, 3544-3546, (2012) · Zbl 1258.05037
[12] Huang, P.; Wong, T.; Zhu, X., Weighted-1-antimagic graphs of prime power order, Discrete Math., 312, 14, 2162-2169, (2012) · Zbl 1244.05186
[13] 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
[14] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colors, J. Combin. Theory Ser. B, 91, 1, 151-157, (2004) · Zbl 1042.05045
[15] Král, D.; Stacho, L., Coloring plane graphs with independet crossings, J. Graph Theory., 64, 3, 184-205, (2010) · Zbl 1208.05019
[16] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688, (2013) · Zbl 1325.05083
[17] 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
[18] Loeb, S.; Tang, Y., Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discrete Math., 340, 2, 58-62, (2017) · Zbl 1351.05083
[19] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 1-12, (2013)
[20] Przybylo, J., Irregularity strength of regular graphs, Electron. J. Combin., 15, 1, R82, (2008) · Zbl 1163.05329
[21] Przybylo, J., Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23, 1, 511-516, (2009) · Zbl 1216.05135
[22] Przybylo, J.; Woźniak, M., On a 1, 2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 1, 101-108, (2010) · Zbl 1250.05093
[23] Przybylo, J.; Woźniak, M., Total weight choosability of graphs, Electron. J. Combin., 18, P112, (2011) · Zbl 1217.05202
[24] Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theor. Comput. Sci., 609, 162-170, (2016) · Zbl 1331.05084
[25] Scheim, E., The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Math., 8, 377-382, (1974) · Zbl 0281.05103
[26] Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim., 27, 2, 379-396, (2014) · Zbl 1319.90076
[27] Wang, J. H.; Ma, Q. L.; Han, X., Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sinica (Engl. Ser.), 31, 2, 216-224, (2015) · Zbl 1317.05065
[28] Wang, W.; Wang, P., On adjacent-vertex-distinguishing total coloring of K4-minor free graphs, Sci. China Ser. A, 39, 12, 1462-1472, (2009)
[29] Wang, Y.; Wang, W., Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Comb. Optim., 19, 123-133, (2010) · Zbl 1216.05039
[30] Wong, T.; Zhu, X., Total weight choosability of graphs, J. Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161
[31] Wong, T.; Zhu, X., Antimagic labelling of vertex weighted graphs, J. Graph Theory, 70, 3, 348-359, (2012) · Zbl 1244.05192
[32] Wong, T.; Zhu, X., Antimagic labelling of vertex weighted graphs, J. Graph Theory, 70, 3, 348-359, (2012) · Zbl 1244.05192
[33] Xu, R. Y.; Wu, J.; Xu, J., Neighbor sum distinguishing total coloring of graphs embedded in surfaces of nonnegative Euler characteristic, J. Comb. Optim., 31, 1430-1442, (2016) · Zbl 1339.05149
[34] Zhang, Z.; Chen, 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
[35] Zhang, X.; Wu, J., On edge colorings of 1-planar graphs, Inform. Process. Lett., 111, 3, 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. 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.