Planar graphs have two-coloring number at most 8

Abstrakt

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.

Klíčová slova

• Planar graph
• Two-colouring number