Maximum average degree of list-edge-critical graphs and Vizing's conjecture

Joshua Harrelson (Faculty of Mathematics and Statistics, Middle Georgia State University, United States)
Hannah Reavis (Department of Mathematics and Statistics, Middle Georgia State University, United States)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 10, No 2 (2022): Electronic Journal of Graph Theory and Applications

Vizing conjectured that χ′ℓ(G)≤Δ + 1 for all graphs. For a graph G and nonnegative integer k, we say G is a k-list-edge-critical graph if χ′ℓ(G)>k, but χ′ℓ(G − e)≤k for all e ∈ E(G). We use known results for list-edge-critical graphs to verify Vizing’s conjecture for G with mad(G)<(Δ + 3)/2 and Δ ≤ 9.