The edge colorings of $K_5$-minor free graphs

Abstract

In 1965, Vizing proved that every planar graph $G$ with maximum degree $\Delta \ge 8$ is edge $\Delta$-colorable. It is also proved that every planar graph $G$ with maximum degree $\Delta =7$ is edge $\Delta$-colorable by Sanders and Zhao, independently by Zhang. In this paper, we extend the above results by showing that every $K_5$-minor free graph with maximum degree $\Delta$ at least seven is edge $\Delta$-colorable.

14 pages, 1 figure