Irreducible 4-critical Triangle-free Toroidal Graphs


The theory of Dvořák, Král', and Thomas shows that a $4$-critical triangle-free graph embedded in the torus has only a bounded number of faces of length greater than $4$ and that the size of these faces is also bounded. We study the natural reduction in such embedded graphs - identification of opposite vertices in $4$-faces. We give a computer-assisted argument showing that there are exactly four $4$-critical triangle-free irreducible toroidal graphs in which this reduction cannot be applied without creating a triangle. Using this result, we show that every $4$-critical triangle-free graph embedded in the torus has at most four $5$-faces, or a $6$-face and two $5$-faces, or a $7$-face and a $5$-face, in addition to at least seven $4$-faces. This result serves as a basis for the exact description of $4$-critical triangle-free toroidal graphs, which we present in a followup paper.

note: There will be another paper extending this work soon.

paper link

Link to arXiv



compliling and running

Implementation is written in c++/11

examples of command on Linux:

source files

main planar, crafting dfs

output format

The graphs on the output are ecoded as following:

output example