Geodesic
Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 1, pp. 111-124
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2021.0333-20
Classification : 05C10, 05C15
Keywords: IC-planar graph; neighbor sum distinguishing list total coloring; Combinatorial Nullstellensatz; discharging method 
@article{10_21136_CMJ_2021_0333_20,
     author = {Zhang, Donghan},
     title = {Neighbor sum distinguishing list total coloring  of {IC-planar} graphs without 5-cycles},
     journal = {Czechoslovak Mathematical Journal},
     pages = {111--124},
     year = {2022},
     volume = {72},
     number = {1},
     doi = {10.21136/CMJ.2021.0333-20},
     mrnumber = {4389109},
     zbl = {07511556},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0333-20/}
}
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
SP  - 111
EP  - 124
VL  - 72
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0333-20/
DO  - 10.21136/CMJ.2021.0333-20
LA  - en
ID  - 10_21136_CMJ_2021_0333_20
ER  - 
%0 Journal Article
%A Zhang, Donghan
%T Neighbor sum distinguishing list total coloring  of IC-planar graphs without 5-cycles
%J Czechoslovak Mathematical Journal
%D 2022
%P 111-124
%V 72
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0333-20/
%R 10.21136/CMJ.2021.0333-20
%G en
%F 10_21136_CMJ_2021_0333_20
Zhang, Donghan. Neighbor sum distinguishing list total coloring  of IC-planar graphs without 5-cycles. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 1, pp. 111-124. doi: 10.21136/CMJ.2021.0333-20

[1] Albertson, M. O.: Chromatic number, independent ratio, and crossing number. Ars Math. Contemp. 1 (2008), 1-6. | DOI | MR | JFM

[2] Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8 (1999), 7-29. | DOI | MR | JFM

[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). | DOI | MR | JFM

[4] Pilśniak, M., Woźniak, M.: On the total-neighbor-distinguishing index by sums. Graphs Comb. 31 (2015), 771-782. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

Cité par Sources :