Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm
Preprint
Abstract
We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Fine Structure of 4-Critical Triangle-Free Graphs III. General SurfacesSIAM Journal on Discrete Mathematics, 2018
- Three-coloring triangle-free planar graphs in linear timeACM Transactions on Algorithms, 2011
- The chromatic number of a graph of girth 5 on a fixed surfaceJournal of Combinatorial Theory, Series B, 2003
- Subgraph Isomorphism in Planar Graphs and Related ProblemsJournal of Graph Algorithms and Applications, 1999
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary SurfaceSIAM Journal on Discrete Mathematics, 1999
- 4-chromatic projective graphsJournal of Graph Theory, 1996
- A separator theorem for graphs of bounded genusJournal of Algorithms, 1984