arXiv Analytics

Sign in

arXiv:1509.01013 [math.CO]AbstractReferencesReviewsResources

Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations

Zdenek Dvorak, Daniel Kral, Robin Thomas

Published 2015-09-03Version 1

We give a linear-time algorithm to decide 3-colorability (and find a 3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm also allows to prescribe the coloring for a bounded number of vertices.

Comments: 28 pages, no figures
Categories: math.CO, cs.DM
Subjects: 05C85, 05C15, F.2.2, G.2.2
Related articles: Most relevant | Search more
arXiv:1302.2158 [math.CO] (Published 2013-02-08, updated 2016-01-06)
Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk
arXiv:1402.4710 [math.CO] (Published 2014-02-19, updated 2019-04-16)
Three-coloring triangle-free graphs on surfaces III. Graphs of girth five
arXiv:2307.10661 [math.CO] (Published 2023-07-20)
Mutual-visibility in distance-hereditary graphs: a linear-time algorithm

Links

Toolbox