Weak degeneracy of the square of the line graph of a subcubic graph

Yanling Zheng; Jingxiang He; Yanling Zheng; Jingxiang He

doi:10.3934/math.2025933

AIMS Mathematics

2025, Volume 10, Issue 9: 20891-20908. doi: 10.3934/math.2025933

Previous Article Next Article

Research article Special Issues

Weak degeneracy of the square of the line graph of a subcubic graph

Yanling Zheng ^{1
,
,},
Jingxiang He ²

1.
School of Science, Zhejiang University of Science and Technology, Hangzhou 310023, China
2.
School of Mathematical Sciences, Zhejiang Normal University, Jinhua 321004, China

Received: 13 May 2025 Revised: 27 August 2025 Accepted: 28 August 2025 Published: 10 September 2025
MSC : 05C15, 05C10

Weak degeneracy is a refined variation of degeneracy that retains many of the useful structural properties of degeneracy, such as facilitating efficient graph orientation, enabling compact representations, and supporting algorithmic applications in graph theory. We focus on the Erdős-Nešetřil Conjecture from the prespective of weak degeneracy. In this paper, we prove that for every subcubic graph $ G $ with a maximun average degree less than $ \frac{33}{16} $, $ \frac{27}{11} $, $ \frac{13}{5} $, and $ \frac{36}{13} $, the weak degeneracy of the corresponding graph $ (L(G))^2 $ is at most $ 5 $, $ 6 $, $ 7 $, and $ 8 $, respectively, where $ (L(G))^2 $ is the square of the line graph of $ G $.
- weak degeneracy,
- strong chromatic index,
- subcubic graph
Citation: Yanling Zheng, Jingxiang He. Weak degeneracy of the square of the line graph of a subcubic graph[J]. AIMS Mathematics, 2025, 10(9): 20891-20908. doi: 10.3934/math.2025933

Related Papers:

Abstract

Weak degeneracy is a refined variation of degeneracy that retains many of the useful structural properties of degeneracy, such as facilitating efficient graph orientation, enabling compact representations, and supporting algorithmic applications in graph theory. We focus on the Erdős-Nešetřil Conjecture from the prespective of weak degeneracy. In this paper, we prove that for every subcubic graph $ G $ with a maximun average degree less than $ \frac{33}{16} $, $ \frac{27}{11} $, $ \frac{13}{5} $, and $ \frac{36}{13} $, the weak degeneracy of the corresponding graph $ (L(G))^2 $ is at most $ 5 $, $ 6 $, $ 7 $, and $ 8 $, respectively, where $ (L(G))^2 $ is the square of the line graph of $ G $.

References

[1]	L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math., 108 (1992), 231–252. https://doi.org/10.1016/0012-365X(92)90678-9 doi: 10.1016/0012-365X(92)90678-9
[2]	A. Bernshteyn, E. Lee, Weak degeneracy of graphs, J. Graph Theory, 103 (2023), 607–634. https://doi.org/10.1002/jgt.22938 doi: 10.1002/jgt.22938
[3]	M. Bonamy, T. Perrett, L. Postle, Colouring graphs with sparse neighbourhoods: bounds and applications, J. Comb. Theory Ser. B, 155 (2022), 278–317. https://doi.org/10.1016/j.jctb.2022.01.009 doi: 10.1016/j.jctb.2022.01.009
[4]	Z. Dvořák, L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Comb. Theory Ser. B, 129 (2018), 38–54. https://doi.org/10.1016/j.jctb.2017.09.001 doi: 10.1016/j.jctb.2017.09.001
[5]	P. Erdős, J. Nešetřil, Irregularities of partitions, Ed.G.Halász and VT Sós, 1989,162–163. https://doi.org/10.1007/978-3-642-61324-1
[6]	J. L. Fouquet, J. L. Jolivet, Strong edge-coloring of graphs and applications to multi-k-gons, Ars Comb., 16-A (1983), 141–150.
[7]	D. Hudák, B. Lužar, R. Soták, R. Škrekovski, Strong edge-coloring of cubic planar graphs, Discrete Math., 324 (2014), 41–49. https://doi.org/10.1016/j.disc.2014.02.002 doi: 10.1016/j.disc.2014.02.002
[8]	M. Han, T. Wang, J. Wu, H. Zhou, X. Zhu, Weak degeneracy of planar graphs and locally planar graphs, Electron. J. Comb., 30 (2023), 1–17. https://doi.org/10.37236/11749 doi: 10.37236/11749
[9]	H. Hocquard, M. Montassier, A. Raspaud, P. Valicow, On strong edge-colouring of subcubic graphs, Discrete Appl. Math., 161 (2013), 2467–2469. https://doi.org/10.1016/j.dam.2013.05.021 doi: 10.1016/j.dam.2013.05.021
[10]	H. Hocquard, P. Valicow, Strong edge colouring of subcubic graphs, Discrete Appl. Math., 159 (2011), 1650–1657. https://doi.org/10.1016/j.dam.2011.06.015 doi: 10.1016/j.dam.2011.06.015
[11]	P. Horák, H. Qing, W. T. Trotter, Induced matching in cubic graphs, J. Graph Theory, 17 (1993), 151–160. https://doi.org/10.1002/jgt.3190170204 doi: 10.1002/jgt.3190170204
[12]	M. Huang, M. Santana, G. Yu, Strong chromatic index of graphs with maximum degree four, Electron. J. Comb., 25 (2018), 1–24. https://doi.org/10.37236/7016 doi: 10.37236/7016
[13]	E. Hurley, R. J. Verclos, R. J. Kang, An improved procedure for colouring graphs of bounded local density, In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2021,135–148.
[14]	H. Ma, Z. Miao, H. Zhu, J. H. Zhang, R. Luo, Strong list edge coloring of subcubic graphs, Math. Prol. Eng., 2013, 316501. https://doi.org/10.1155/2013/316501
[15]	M. Molloy, B. Reed, A bound on the strong chromatic index of a graph, J. Comb. Theory, Ser. B, 69 (1997), 103–109. https://doi.org/10.1006/jctb.1997.1724 doi: 10.1006/jctb.1997.1724
[16]	U. Schauz, Mr. Paint and Mrs. Correct, Electron. J. Comb., 16 (2009), 1–18. https://doi.org/10.37236/166 doi: 10.37236/166
[17]	B. Zhang, Y. Chang, J. Hu, M. Ma, D. Yang, List strong edge-coloring of graphs with maximum degree 4, Discrete Math., 343 (2020), 111854. https://doi.org/10.1016/j.disc.2020.111854 doi: 10.1016/j.disc.2020.111854
[18]	H. Zhu, Z. Miao, On strong list edge coloring of subcubic graphs, Discrete Math., 333 (2014), 6–13. https://doi.org/10.1016/j.disc.2014.06.004 doi: 10.1016/j.disc.2014.06.004
[19]	X. Zhu, On-line list colouring of graphs, Electron. J. Combin., 16 (2009), 1–16. https://doi.org/10.37236/216 doi: 10.37236/216

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)