Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles

Donghan Zhang

Czechoslovak Mathematical Journal (2022)

  • Volume: 72, Issue: 1, page 111-124
  • ISSN: 0011-4642

Abstract

top
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 φ of G is a proper total coloring of G such that ∑ z ∈ E G ( u ) ∪ { u } φ ( z ) ≠ ∑ z ∈ E G ( v ) ∪ { v } φ ( z ) for each edge u v ∈ E ( G ) . Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree Δ admits an NSD total ( Δ + 3 ) -coloring. We prove that the list version of this conjecture holds for any IC-planar graph with Δ ≥ 11 but without 5 -cycles by applying the Combinatorial Nullstellensatz.

How to cite

top

Zhang, Donghan. "Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles." Czechoslovak Mathematical Journal 72.1 (2022): 111-124. <http://eudml.org/doc/298063>.

@article{Zhang2022,
abstract = {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 \lbrace u\rbrace \}\phi (z)\ne \sum _\{z\in E_\{G\}(v)\cup \lbrace v\rbrace \}\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 \ge 11$ but without $5$-cycles by applying the Combinatorial Nullstellensatz.},
author = {Zhang, Donghan},
journal = {Czechoslovak Mathematical Journal},
keywords = {IC-planar graph; neighbor sum distinguishing list total coloring; Combinatorial Nullstellensatz; discharging method},
language = {eng},
number = {1},
pages = {111-124},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles},
url = {http://eudml.org/doc/298063},
volume = {72},
year = {2022},
}

TY - JOUR
AU - Zhang, Donghan
TI - Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles
JO - Czechoslovak Mathematical Journal
PY - 2022
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 72
IS - 1
SP - 111
EP - 124
AB - 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 \lbrace u\rbrace }\phi (z)\ne \sum _{z\in E_{G}(v)\cup \lbrace v\rbrace }\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 \ge 11$ but without $5$-cycles by applying the Combinatorial Nullstellensatz.
LA - eng
KW - IC-planar graph; neighbor sum distinguishing list total coloring; Combinatorial Nullstellensatz; discharging method
UR - http://eudml.org/doc/298063
ER -

References

top
  1. Albertson, M. O., 10.26493/1855-3974.10.2d0, Ars Math. Contemp. 1 (2008), 1-6. (2008) Zbl1181.05032MR2434266DOI10.26493/1855-3974.10.2d0
  2. Alon, N., 10.1017/S0963548398003411, Comb. Probab. Comput. 8 (1999), 7-29. (1999) Zbl0920.05026MR1684621DOI10.1017/S0963548398003411
  3. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5, Graduate Texts in Mathematics 244. Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-5
  4. Pilśniak, M., Woźniak, M., 10.1007/s00373-013-1399-4, Graphs Comb. 31 (2015), 771-782. (2015) Zbl1312.05054MR3338032DOI10.1007/s00373-013-1399-4
  5. Qu, C., Wang, G., Yan, G., Yu, X., 10.1007/s10878-015-9911-9, J. Comb. Optim. 32 (2016), 906-916. (2016) Zbl1348.05082MR3544074DOI10.1007/s10878-015-9911-9
  6. Song, C., Jin, X., Xu, C., 10.1016/j.dam.2019.12.023, Discrete Appl. Math. 279 (2020), 202-209. (2020) Zbl1439.05095MR4092640DOI10.1016/j.dam.2019.12.023
  7. Song, C., Xu, C., 10.1007/s10878-019-00467-1, J. Comb. Optim. 39 (2020), 293-303. (2020) Zbl1434.05057MR4047108DOI10.1007/s10878-019-00467-1
  8. Song, W., Duan, Y., Miao, L., 10.1007/s10114-020-9189-4, Acta Math. Sin., Engl. Ser. 36 (2020), 292-304. (2020) Zbl1439.05096MR4072704DOI10.1007/s10114-020-9189-4
  9. Song, W., Miao, L., Duan, Y., 10.7151/dmgt.2145, Discuss. Math., Graph Theory 40 (2020), 331-344. (2020) Zbl1430.05023MR4041985DOI10.7151/dmgt.2145
  10. Wang, J., Cai, J., Qiu, B., 10.1016/j.tcs.2016.11.003, Theor. Comput. Sci. 661 (2017), 1-7. (2017) Zbl1357.05027MR3591208DOI10.1016/j.tcs.2016.11.003
  11. Yang, D., Sun, L., Yu, X., Wu, J., Zhou, S., 10.1016/j.amc.2017.06.002, Appl. Math. Comput. 314 (2017), 456-468. (2017) Zbl1426.05051MR3683886DOI10.1016/j.amc.2017.06.002

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.