Coloring triangle-free graphs on surfaces

Abstract

We present a linear-time algorithm for 3-coloring triangle-free graphs embedded in a fixed surface.

Keywords

• Coloring graphs
• graphs on surfaces