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

Joshua Harrelson, Hannah Reavis

Abstract


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.


Keywords


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

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.4

References

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). https://doi.org/10.1137/130927449

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. https://doi.org/10.1006/jctb.1997.1780

O.V. Borodin, A generalization of Kotzig’s theorem on prescribed edge coloring of planar graphs, Mat. Zametki 48 (1990), 1186-1190. https://doi.org/10.1007/BF01240258

N. Cohen and F. Havet, Planar graphs with maximum degree Δ ≤ 9 are (Δ + 1)-edge-choosable-a short proof, Discrete Math. 310 (2010), 3049-3051. https://doi.org/10.1016/j.disc.2010.07.004

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. https://doi.org/10.1006/jctb.1995.1011

J. Harrelson, J. McDonald, and G. Puleo, List-edge-colouring planar graphs with precoloured edges, European J. of Combin. 75 (2019), 55-65. https://doi.org/10.1016/j.ejc.2018.07.003.

M. Juvan, B. Mohar, and R. Škrekovski, List total colorings of graphs, Combin. Probab. Comput. 7 (1998), 181-188. https://doi.org/10.1017/S0963548397003210

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. https://doi.org/10.1016/j.disc.2009.11.011


Refbacks

  • 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