Irreducible 4-critical Triangle-free Toroidal Graphs

abstract

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

implementation

link

compliling and running

Implementation is written in c++/11

examples of command on Linux:

• compile: g++ -std=c++11 main.cpp -o [program-filename]
• run: ./[program-filename]

source files

• the main method starting the enumeration process

• simple library for working with graphs embedded into surfaces and a few tools for graph crafting specially designed for this program
• all graph operations and representations are contained here

• implementation of several versions of dfs graph search used in the enumeration (including face-based dfs, cycle detection, ...)

engines
• the main header file containing definitions of all key modules of the enumeration
• implementations of these modules are split into multiple .cpp files
  • EngineCommon - core module, implements main methods and functionality shared among modules
  • ExpansionEngine - implements expansion operation
  • LinkageEngine - implements linkage operation
  • Box - implementation of optimized memory allocation
  • Stats - statistics tracing while the enumeration is running

output format

The graphs on the output are ecoded as following:

• On the first line there is graphs [id] followed by the list of present face-lengths and how many faces have each length
• On the secont line, there is a list of vertices as they appear around one of the 4-faces
• Then there are several lines, each corresponding to a vertex (with id in brackets) and a list of its neighbors as they appear around it in the drawing (clockwise)
• For a more compact representation in a computer-readable form, change command in EngineCommon.cpp/EngineCommon::exploreResults/lines12-14 use prepared line of code instead of the currently used one

output example