Planar graphs have two-coloring number at most 8

Abstract

We prove that the two-coloring number of any planar graph is at most 8. This resolves a question of Kierstead et al. (2009) [3].

The result is optimal.

Keywords

• Planar graph
• Two-colouring number