论文标题
4-临界三角形的环形图的表征
Characterization of 4-critical triangle-free toroidal graphs
论文作者
论文摘要
我们以186个“模板”的形式（带有任意四边形填充的某些面孔的图形）的形式确切地表征了在圆环中绘制的无三角形图的3色性表征，因此，只有在包含匹配模板的一个子段时，该类别的图形就不可能进行3色。结果，我们显示了在圆环中绘制的每个无三角形图，至少六个是3色的，这是一种用于无三角形圆环图的有效3色算法中的关键属性。
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.
