Planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable

zbMATH Open1293.05131arXiv1303.4025MaRDI QIDQ5419972FDOQ5419972

Authors: Marthe Bonamy 

Publication date: 11 June 2014

Abstract: We consider the problem of list edge coloring for planar graphs. Edge coloring is the problem of coloring the edges while ensuring that two edges that are incident receive different colors. A graph is k-edge-choosable if for any assignment of k colors to every edge, there is an edge coloring such that the color of every edge belongs to its color assignment. Vizing conjectured in 1965 that every graph is (D+1)-edge-choosable, where D is the maximum degree. In 1990, Borodin solved the conjecture for planar graphs with maximum degree at least 9, and asked whether the bound could be lowered to 8. We prove here that planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable.

Full work available at URL: https://arxiv.org/abs/1303.4025

Recommendations

• Planar graphs with \(\Delta\geq 8\) are (\(\Delta+1\))-edge-choosable
• Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable
• Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta +1)\)-edge-choosable--a short proof
• Plane graphs are entirely \((\Delta + 5)\)-choosable
• Planar graphs without \(\{4, 6, 8\}\)-cycles are 3-choosable
• Every planar graph without adjacent cycles of length at most 8 is 3-choosable
• Planar graphs without 3-, 7-, and 8-cycles are 3-choosable
• Planar graphs with \(\Delta \geq 7\) and no triangle adjacent to a \(C_{4}\) are minimally edge and total choosable
• scientific article; zbMATH DE number 5983740
• A Note on Edge Choosability and Degeneracy of Planar Graphs

zbMATH Keywords

list edge coloring

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cited In (9)

• Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable
• Title not available (Why is that?)
• A note on the minimum number of choosability of planar graphs
• Planar graphs with \(\Delta\geq 8\) are (\(\Delta+1\))-edge-choosable
• List-edge-colouring planar graphs with precoloured edges
• Title not available (Why is that?)
• Edge-colouring eight-regular planar graphs
• Signed planar graphs with \(\Delta \geq 8\) are \(\Delta\)-edge-colorable
• A Generalization of Kotzig’s Theorem and Its Application

This page was built for publication: Planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419972)