Article
| Title: | Strict neighbor-distinguishing index of planar graphs without 4-cycles (English) |
| Author: | Jing, Puning |
| Author: | Wang, Weifan |
| Author: | Wu, Qingqin |
| Author: | Zheng, Lina |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 76 |
| Issue: | 3 |
| Year: | 2026 |
| Pages: | 763-786 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | A proper edge coloring of a graph $G$ is strict neighbor-distinguishing if for any two adjacent vertices $u$ and $v$, the set of colors used on the edges incident to $u$ and the set of colors used on the edges incident to $v$ are not included with each other. The strict neighbor-distinguishing index of $G$ is the minimum number $\chi '_{\rm snd}(G)$ of colors in a strict neighbor-distinguishing edge coloring of $G$. It was conjectured that every simple graph $G$ without leaves has $\chi '_{\rm snd}(G)\le 2\Delta $ except a special graph $H_{\Delta }$. We show that if $G$ is a planar graph without 4-cycles, then $\chi '_{\rm snd}(G)\le \Delta +300$. (English) |
| Keyword: | strict neighbor-distinguishing edge coloring |
| Keyword: | local strict neighbor-distinguishing edge coloring |
| Keyword: | planar graph |
| Keyword: | cycle |
| MSC: | 05C15 |
| DOI: | 10.21136/CMJ.2026.0532-24 |
| . | |
| Date available: | 2026-09-11T13:10:57Z |
| Last updated: | 2026-09-14 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153727 |
| . | |
| Reference: | [1] Akbari, S., Bidkhori, H., Nosrati, N.: $r$-strong edge colorings of graphs.Discrete Math. 306 (2006), 3005-3010. Zbl 1112.05035, MR 2273128, 10.1016/j.disc.2004.12.027 |
| Reference: | [2] Gu, J., Wang, W., Wang, Y., Wang, Y.: Strict neighbor-distinguishing index of subcubic graphs.Graphs Comb. 37 (2021), 355-368. Zbl 1459.05078, MR 4197385, 10.1007/s00373-020-02246-w |
| Reference: | [3] Gu, J., Wang, Y., Wang, W., Zheng, L.: Strict neighbor-distinguishing index of $K_4$-minor- free graphs.Discrete Appl. Math. 329 (2023), 87-95. Zbl 1508.05154, MR 4538357, 10.1016/j.dam.2023.01.017 |
| Reference: | [4] Hatami, H.: $\Delta +300$ is a bound on the adjacent vertex distinguishing edge chromatic number.J. Comb. Theory, Ser. B 95 (2005), 246-256. Zbl 1075.05034, MR 2171364, 10.1016/j.jctb.2005.04.002 |
| Reference: | [5] Huang, N., Tan, Y., Chen, L.: On the inclusion chromatic index of a Halin graph.Discrete Math. 348 (2025), Article ID 114266, 9 pages. Zbl 1558.05050, MR 4799280, 10.1016/j.disc.2024.114266 |
| Reference: | [6] Jing, P., Wang, W., Wang, Y., Zheng, L.: Strict neighbor-distinguishing edge coloring of planar graphs.Sci. Sin. Math. 53 (2023), 523-542 Chinese. 10.1360/SSM-2021-0178 |
| Reference: | [7] Joret, G., Lochet, W.: Progress on the adjacent vertex distinguishing edge coloring conjecture.SIAM J. Discrete Math. 34 (2020), 2221-2238. Zbl 1453.05036, MR 4169257, 10.1137/18M1200427 |
| Reference: | [8] Przybyło, J., Kwaśny, J.: On the inclusion chromatic index of a graph.J. Graph Theory 97 (2021), 5-20. Zbl 1522.05138, MR 4267024, 10.1002/jgt.22636 |
| Reference: | [9] Vučković, B.: Edge-partitions of graphs and their neighbor-distinguishing index.Discrete Math. 340 (2017), 3092-3096. Zbl 1370.05175, MR 3698098, 10.1016/j.disc.2017.07.005 |
| Reference: | [10] Wang, W., Jing, P., Gu, J., Wang, Y.: Local neighbor-distinguishing index of graphs.Bull. Malays. Math. Sci. Soc. (2) 46 (2023), Article ID 83, 16 pages. Zbl 1509.05079, MR 4555354, 10.1007/s40840-023-01474-6 |
| Reference: | [11] Wang, W., Zheng, L., Gu, J., Wang, Y., Huo, J.: Strict neighbor-distinguishing index of outerplanar graphs.Discrete Appl. Math. 370 (2025), 1-10. Zbl 1562.05063, MR 4876878, 10.1016/j.dam.2025.03.002 |
| Reference: | [12] Wang, Y., Wang, W., Huo, J.: Some bounds on the neighbor-distinguishing index of graphs.Discrete Math. 338 (2015), 2006-2013. Zbl 1314.05082, MR 3357786, 10.1016/j.disc.2015.05.007 |
| Reference: | [13] Zhang, Z., Liu, L., Wang, J.: Adjacent strong edge coloring of graphs.Appl. Math. Lett. 15 (2002), 623-626. Zbl 1008.05050, MR 1889513, 10.1016/S0893-9659(02)80015-5 |
| Reference: | [14] Zhu, E., Wang, Z., Zhang, Z.: On the Smarandachely-adjacent-vertex edge coloring of some double graphs.J. Shandong Univ., Nat. Sci. 44 (2009), 25-29 Chinese. Zbl 1212.05108 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
