2020/09/02 by Zdenĕk Dvořák, Dvořák, Zdeněk, Jakub Pekárek +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2009.00864
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.