Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
strict neighbor-distinguishing edge coloring; local strict neighbor-distinguishing edge coloring; planar graph; cycle
strict neighbor-distinguishing edge coloring; local strict neighbor-distinguishing edge coloring; planar graph; cycle
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$.
References:
[1] Akbari, S., Bidkhori, H., Nosrati, N.: $r$-strong edge colorings of graphs. Discrete Math. 306 (2006), 3005-3010. DOI 10.1016/j.disc.2004.12.027 | MR 2273128 | Zbl 1112.05035
[2] Gu, J., Wang, W., Wang, Y., Wang, Y.: Strict neighbor-distinguishing index of subcubic graphs. Graphs Comb. 37 (2021), 355-368. DOI 10.1007/s00373-020-02246-w | MR 4197385 | Zbl 1459.05078
[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. DOI 10.1016/j.dam.2023.01.017 | MR 4538357 | Zbl 1508.05154
[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. DOI 10.1016/j.jctb.2005.04.002 | MR 2171364 | Zbl 1075.05034
[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. DOI 10.1016/j.disc.2024.114266 | MR 4799280 | Zbl 1558.05050
[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. DOI 10.1360/SSM-2021-0178
[7] Joret, G., Lochet, W.: Progress on the adjacent vertex distinguishing edge coloring conjecture. SIAM J. Discrete Math. 34 (2020), 2221-2238. DOI 10.1137/18M1200427 | MR 4169257 | Zbl 1453.05036
[8] Przybyło, J., Kwaśny, J.: On the inclusion chromatic index of a graph. J. Graph Theory 97 (2021), 5-20. DOI 10.1002/jgt.22636 | MR 4267024 | Zbl 1522.05138
[9] Vučković, B.: Edge-partitions of graphs and their neighbor-distinguishing index. Discrete Math. 340 (2017), 3092-3096. DOI 10.1016/j.disc.2017.07.005 | MR 3698098 | Zbl 1370.05175
[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. DOI 10.1007/s40840-023-01474-6 | MR 4555354 | Zbl 1509.05079
[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. DOI 10.1016/j.dam.2025.03.002 | MR 4876878 | Zbl 1562.05063
[12] Wang, Y., Wang, W., Huo, J.: Some bounds on the neighbor-distinguishing index of graphs. Discrete Math. 338 (2015), 2006-2013. DOI 10.1016/j.disc.2015.05.007 | MR 3357786 | Zbl 1314.05082
[13] Zhang, Z., Liu, L., Wang, J.: Adjacent strong edge coloring of graphs. Appl. Math. Lett. 15 (2002), 623-626. DOI 10.1016/S0893-9659(02)80015-5 | MR 1889513 | Zbl 1008.05050
[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
Search
Partner of
