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

Joshua Harrelson, Hannah Reavis


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.


list-edge-coloring \sep maximum average degree \sep discharging

Full Text:




M. Bonamy, Planar graphs with Δ ≥ 8 are (Δ + 1)-edge-choosable, Seventh Euro. Conference in Comb., Graph Theory and App., CRM series, Edizioni della Normale 16 (2013).

O.V. Borodin, A. V. Kostochka, and D. R. Woodall, List edge and list total colorings of multigraphs, J. Combin. Theory Ser. B 71 (1997), 184-204.

O.V. Borodin, A generalization of Kotzig’s theorem on prescribed edge coloring of planar graphs, Mat. Zametki 48 (1990), 1186-1190.

N. Cohen and F. Havet, Planar graphs with maximum degree Δ ≤ 9 are (Δ + 1)-edge-choosable-a short proof, Discrete Math. 310 (2010), 3049-3051.

P. Erdõs, A. Rubin, and H. Taylor, Choosability in graphs. Congr. Numer. 26 (1979), 125-157.

F. Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Ser. B 63 (1995), 153-158.

J. Harrelson, J. McDonald, and G. Puleo, List-edge-colouring planar graphs with precoloured edges, European J. of Combin. 75 (2019), 55-65.

M. Juvan, B. Mohar, and R. Škrekovski, List total colorings of graphs, Combin. Probab. Comput. 7 (1998), 181-188.

V.G. Vizing, Colouring the vertices of a graph with prescribed colours, Diskret. Analiz 29 (1976), 3-10. (In Russian)

V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964), 25–30.

D. Woodall, The average degree of a multigraph critical with respect to edge or total choosability, Discrete Math. 310 (2010), no. 6-7, 1167-1171.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats