Spelling suggestions: "subject:"torus zbarvení coloring graft graph"" "subject:"torus zbarvení coloring grafo graph""
1 |
3-barevnost grafů na toru / 3-Coloring Graphs on TorusPekárek, Jakub January 2017 (has links)
The theory of Dvořák et al. 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 demonstrate several properties that are necessary for every triangle-free graph embedded in the torus to be 4-critical. Most importantly we demonstrate that every such graph 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.
|
Page generated in 0.1202 seconds