Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777097 | Electronic Notes in Discrete Mathematics | 2017 | 7 Pages |
Abstract
The theory of DvoÅák, Král', and Thomas [DvoÅák, Z., D. Král', and R. Thomas, Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs, ArXiv e-prints 1404.6356v2 (Jan. 2015)] 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
ZdenÄk DvoÅák, Jakub Pekárek,