arXiv Analytics

Sign in

arXiv:1506.01412 [math.CO]AbstractReferencesReviewsResources

Planar graphs have two-coloring number at most 8

Zdeněk Dvořák, Adam Kabela, Tomáš Kaiser

Published 2015-06-03Version 1

We prove that the two-colouring number of any planar graph is at most 8. This resolves a question of Kierstead et al. [SIAM J. Discrete Math.~23 (2009), 1548--1560]. The result is optimal.

Categories: math.CO
Subjects: 05C15, 05C10, G.2.2
Related articles: Most relevant | Search more
arXiv:1802.04179 [math.CO] (Published 2018-02-12)
Planar graphs without cycles of length 4 or 5 are (11:3)-colorable
arXiv:1209.0366 [math.CO] (Published 2012-09-03, updated 2016-02-03)
5-list-coloring planar graphs with distant precolored vertices
arXiv:0909.3286 [math.CO] (Published 2009-09-17)
O-cycles, vertex-oriented graphs, and the four colour theore

Links

Toolbox