Characterization of 4-critical triangle-free toroidal graphs

Abstrakt

We give an exact characterization of 3-colorability of triangle free graphs drawn in the torus, in the form of 186 "templates" (graphs with certain faces filled by arbitrary quadrangulations) such that a graph from this class is not 3-colorable if and only if it contains a subgraph matching one of the templates. As a consequence, we show every triangle-free graph drawn in the torus with edge-width at least six is 3-colorable, a key property used in an efficient 3-colorability algorithm for triangle-free toroidal graphs. (c) 2022 Elsevier Inc.

All rights reserved.

Klíčová slova

• Coloring
• Torus
• Triangle-free