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

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 $.

Topics & Concepts