2011
Every plane graph of maximum degree 8 has an edge-face 9-colouring.
Publication
Publication
SIAM Journal on Discrete Mathematics , Volume 25 - Issue 2 p. 514- 533
An edge-face coloring of a plane graph with edge set $E$ and face set $F$ is a coloring of the elements of $E\cup F$ such that adjacent or incident elements receive different colors. Borodin proved that every plane graph of maximum degree $\Delta \ge 10$ can be edge-face colored with $\Delta + 1$ colors. Borodin’s bound was recently extended to the case where $\Delta = 9$. In this paper, we extend it to the case $\Delta = 8$.
Additional Metadata | |
---|---|
, , | |
S.I.A.M. | |
SIAM Journal on Discrete Mathematics | |
Kang, R., Sereni, J.-S., & Stehlík, M. (2011). Every plane graph of maximum degree 8 has an edge-face 9-colouring. SIAM Journal on Discrete Mathematics, 25(2), 514–533. |