×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total choosability of IC-planar graphs. (English) Zbl 1430.05023
Summary: Two distinct crossings are independent if the end-vertices of the crossed pair of edges 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, \dots, k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let \(\Sigma_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 \(uv \in E(G)\), \(\Sigma_c(u) \neq \Sigma_c(v)\). The least number \(k\) needed for such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number, denoted by \(\chi^{\prime\prime}_\Sigma ( G )\). In this paper, it is proved that if \(G\) is an IC-planar graph with maximum degree \(\Delta (G)\), then \(ch^{\prime\prime}_\Sigma( G ) \le \max \left\{\Delta(G ) + 3,17\right\}\), where \(ch^{\prime\prime}_\Sigma(G)\) is the neighbor sum distinguishing total choosability of \(G\).

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C62 Graph representations (geometric and intersection representations, etc.)
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M.O. Albertson, Chromatic number, independence ratio, and crossing number, Ars Math. Contemp. 1 (2008) 1-6. · Zbl 1181.05032
[2] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999) 7-29. doi:10.1017/S0963548398003411
[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982). · Zbl 1226.05083
[4] L. Ding, G. Wang and G. Yan, Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz, Sci. China Math. 57 (2014) 1875-1882. doi:10.1007/s11425-014-4796-0 · Zbl 1303.05058
[5] L. Ding, G. Wang, J. Wu and J. Yu, Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Graphs Combin. 33 (2017) 885-900. doi:10.1007/s00373-017-1806-3 · Zbl 1371.05078
[6] A. Dong and G. Wang, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin. (Engl. Ser.) 30 (2014) 703-709. doi:10.1007/s10114-014-2454-7 · Zbl 1408.05061
[7] D. Král and L. Stacho, Coloring plane graphs with independent crossings, J. Graph Theory 64 (2010) 184-205. doi:10.1002/jgt.20448 · Zbl 1208.05019
[8] H. Li, B. Liu and G. Wang, Neighbor sum distinguishing total colorings of K_4-minor free graphs, Front. Math. China 8 (2013) 1351-1366. doi:10.1007/s11464-013-0322-x · Zbl 1306.05066
[9] H. Li, L. Ding, B. Liu and G. Wang, Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim. 30 (2015) 675-688. doi:10.1007/s10878-013-9660-6 · Zbl 1325.05083
[10] S. Loeb, J. Przybyło and Y. Tang, Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discrete Math. 340 (2017) 58-62. doi:10.1016/j.disc.2016.08.012 · Zbl 1351.05083
[11] M. Pilśniak and M. Woźniak, On the total-neighbor-distinguishing index by sums, Graphs Combin. 31 (2015) 771-782. doi:10.1007/s00373-013-1399-4
[12] C. Qu, G. Wang, J. Wu and X. Yu, On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci. 609 (2016) 162-170. doi:10.1016/j.tcs.2015.09.017 · Zbl 1331.05084
[13] C. Qu, G. Wang, G. Yan and X. Yu, Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim. 32 (2016) 906-916. doi:10.1007/s10878-015-9911-9 · Zbl 1348.05082
[14] D.E. Scheim, The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Math. 8 (1974) 377-382. doi:10.1016/0012-365X(74)90157-5 · Zbl 0281.05103
[15] J. Wang, J. Cai and Q. Ma, Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Appl. Math. 206 (2016) 215-219. doi:10.1016/j.dam.2016.02.003 · Zbl 1335.05051
[16] J. Yao and H. Kong, Neighbor sum distinguishing total choosability of graphs with larger maximum average degree, Ars Combin. 125 (2016) 347-360. · Zbl 1413.05353
[17] X. Zhang and J. Wu, On edge colorings of 1-planar graphs, Inform. Process. Lett. 111 (2011) 124-128. doi:10.1016/j.ipl.2010.11.001 · Zbl 1259.05050
[18] J. Yao, X. Yu, G. Wang and C. Xu, Neighbor sum (set) distinguishing total choosability of d-degenerate graphs, Graphs Combin. 32 (2016) 1611-1620. doi:10.1007/s00373-015-1646-y · Zbl 1342.05052
[19] X. Cheng, D. Huang, G. Wang and J. Wu, Neighbor sum distinguishing total colorings of planar graphs with maximum degree, Discrete Appl. Math. 190-191 (2015) 34-41. doi:10.1016/j.dam.2015.03.013 · Zbl 1316.05041
[20] Y. Lu, M.M. Han and R. Luo, Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring, Discrete Appl. Math. 237 (2018) 109-115. doi:10.1016/j.dam.2017.12.001 · Zbl 1380.05076
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.