Coloring Graphs without Short Non-bounding Cycles
Coloring Graphs without Short Non-bounding Cycles
复制标题
没有短无界循环的着色图
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
B. Mohar
中科院分区：
文献类型：
--
作者：
S. Fisk;B. Mohar
证明了存在一个常数c使得如果G是一个嵌入在亏格g(可定向或不可定向)曲面上的图，且G的一个最短无界圈的长度至少为clog(g+1)，则G是六色的。在对G的周长作额外假设的情况下，类似的结果也适用于三色和四色。
It is shown that there is a constant c such that if G is a graph embedded in a surface of genus g (either orientable or non-orientable) and the length of a shortest non-bounding cycle of G is at least c log(g + 1), then G is six-colorable. A similar result holds for three- and four-colorings under additional assumptions on the girth of G.