Weak degeneracy of the square of K4-minor free graphs

Jing Ye, Jiani Zou and Miaomiao Han

Applied Mathematics and Computation, 2025, vol. 500, issue C

Abstract: A graph G is called weakly f-degenerate with respect to a function f from V(G) to the non-negative integers, if every vertex of G can be successively removed through a series of valid Delete and DeleteSave operations. The weak degeneracy wd(G) is defined as the smallest integer d for which G is weakly d-degenerate, where d is a constant function. It was demonstrated that one plus the weak degeneracy can act as an upper bound for list-chromatic number and DP-chromatic number. Let κ(G2)=Δ(G)+2 if 2≤Δ(G)≤3, and κ(G2)=⌊3Δ(G)2⌋ if Δ(G)≥4. In this paper, we prove that for every K4-minor free graph G, wd(G2)≤κ(G2), which implies that G2 is (κ(G2)+1)-choosable and (κ(G2)+1)-DP-colorable. This work generalizes the result obtained by Lih et al. in [Discrete Mathematics, 269 (2003), 303-309] and Hetherington et al. in [Discrete Mathematics, 308 (2008), 4037-4043].

Keywords: Weak degeneracy; K4-minor free graphs; Square graphs (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300325001663
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:500:y:2025:i:c:s0096300325001663

DOI: 10.1016/j.amc.2025.129439

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().