Publication at Faculty of Mathematics and Physics |
2022
Abstract
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.