Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm (Q2664564)

This paper deals with 3-colorability of triangle-free graphs embedded in a fixed surface. More precisely, it is the last work of a series from the same authors on this topic. In this paper, the authors provide a linear-time algorithm to decide 3-colorability; in case of a positive answer, a quadratic-time algorithm can be used to output a 3-coloring. Such algorithms also allow to set the coloring of a bounded number of vertices in the given graph. \par For Part VI see [the authors, ``Three-coloring triangle-free graphs on surfaces. VI. 3-colorability of quadrangulations'', Preprint, \url{arXiv:1509.01013}].