Every plane graph of maximum degree 8 has an edge-face 9-colouring

Abstract

An edge-face colouring of a plane graph with edge set $E$ and face set $F$ is a colouring of the elements of $E\cup F$ such that adjacent or incident elements receive different colours. Borodin proved that every plane graph of maximum degree $\Delta \ge 10$ can be edge-face coloured with $\Delta +1$ colours. Borodin's bound was recently extended to the case where $\Delta =9$. In this paper, we extend it to the case $\Delta =8$.

arXiv comment29 pages, 1 figure; v2 corrects a contraction error in v1; to appear in SIDMA