Flows on Bidirected Graphs
Flows on Bidirected Graphs
复制标题
DOI：
--
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Matt DeVos
中科院分区：
文献类型：
--
作者：
Matt DeVos
无零流的研究始于Tutte的一个关键观察，即在平面图中，无零k-流与k-着色（以k-张力的形式）是对偶的。Tutte证明了每个没有割边的图都有一个无处为零的5-流。Seymour证明了每一个这样的图都有一个nowhere-zero 6-flow。对于嵌入在高亏格的可定向曲面中的图，流不是染色的对偶，而是局部张力的对偶。根据Seymour定理，可定向曲面上没有明显障碍的图都有无处为零的6-局部张力。Bouchet指出，同样的道理也适用于不可定向的表面。等价地，Bouchet证明了每一个具有非零$\mathbb{Z}$-流的双向图都具有非零6-流。我们的主要结果是，每个这样的图有一个无处为零的12流。
The study of nowhere-zero flows began with a key observation of Tutte that in planar graphs, nowhere-zero k-flows are dual to k-colourings (in the form of k-tensions). Tutte conjectured that every graph without a cut-edge has a nowhere-zero 5-flow. Seymour proved that every such graph has a nowhere-zero 6-flow. For a graph embedded in an orientable surface of higher genus, flows are not dual to colourings, but to local-tensions. By Seymour's theorem, every graph on an orientable surface without the obvious obstruction has a nowhere-zero 6-local-tension. Bouchet conjectured that the same should hold true on non-orientable surfaces. Equivalently, Bouchet conjectured that every bidirected graph with a nowhere-zero $\mathbb{Z}$-flow has a nowhere-zero 6-flow. Our main result establishes that every such graph has a nowhere-zero 12-flow.