Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
IC-planar graph; neighbor sum distinguishing list total coloring; Combinatorial Nullstellensatz; discharging method
IC-planar graph; neighbor sum distinguishing list total coloring; Combinatorial Nullstellensatz; discharging method
Summary:
Let $G=(V(G),E(G))$ be a simple graph and $E_{G}(v)$ denote the set of edges incident with a vertex $v$. A neighbor sum distinguishing (NSD) total coloring $\phi $ of $G$ is a proper total coloring of $G$ such that $\sum _{z\in E_{G}(u)\cup \{u\}}\phi (z)\neq \sum _{z\in E_{G}(v)\cup \{v\}}\phi (z)$ for each edge $uv\in E(G)$. Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree $\Delta $ admits an NSD total $(\Delta +3)$-coloring. We prove that the list version of this conjecture holds for any IC-planar graph with $\Delta \geq 11$ but without $5$-cycles by applying the Combinatorial Nullstellensatz.
References:
[1] Albertson, M. O.: Chromatic number, independent ratio, and crossing number. Ars Math. Contemp. 1 (2008), 1-6. DOI 10.26493/1855-3974.10.2d0 | MR 2434266 | Zbl 1181.05032
[2] Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8 (1999), 7-29. DOI 10.1017/S0963548398003411 | MR 1684621 | Zbl 0920.05026
[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). DOI 10.1007/978-1-84628-970-5 | MR 2368647 | Zbl 1134.05001
[4] Pilśniak, M., Woźniak, M.: On the total-neighbor-distinguishing index by sums. Graphs Comb. 31 (2015), 771-782. DOI 10.1007/s00373-013-1399-4 | MR 3338032 | Zbl 1312.05054
[5] Qu, C., Wang, G., Yan, G., Yu, X.: Neighbor sum distinguishing total choosability of planar graphs. J. Comb. Optim. 32 (2016), 906-916. DOI 10.1007/s10878-015-9911-9 | MR 3544074 | Zbl 1348.05082
[6] Song, C., Jin, X., Xu, C.: Neighbor sum distinguishing total coloring of IC-planar graphs with short cycle restrictions. Discrete Appl. Math. 279 (2020), 202-209. DOI 10.1016/j.dam.2019.12.023 | MR 4092640 | Zbl 1439.05095
[7] Song, C., Xu, C.: Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13. J. Comb. Optim. 39 (2020), 293-303. DOI 10.1007/s10878-019-00467-1 | MR 4047108 | Zbl 1434.05057
[8] Song, W., Duan, Y., Miao, L.: Neighbor sum distinguishing total coloring of triangle free IC-planar graphs. Acta Math. Sin., Engl. Ser. 36 (2020), 292-304. DOI 10.1007/s10114-020-9189-4 | MR 4072704 | Zbl 1439.05096
[9] Song, W., Miao, L., Duan, Y.: Neighbor sum distinguishing total choosability of IC-planar graphs. Discuss. Math., Graph Theory 40 (2020), 331-344. DOI 10.7151/dmgt.2145 | MR 4041985 | Zbl 1430.05023
[10] Wang, J., Cai, J., Qiu, B.: Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles. Theor. Comput. Sci. 661 (2017), 1-7. DOI 10.1016/j.tcs.2016.11.003 | MR 3591208 | Zbl 1357.05027
[11] Yang, D., Sun, L., Yu, X., Wu, J., Zhou, S.: Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10. Appl. Math. Comput. 314 (2017), 456-468. DOI 10.1016/j.amc.2017.06.002 | MR 3683886 | Zbl 1426.05051
Search
Partner of
