Nowhere-zero integral chains and flows in bidirected graphs
Nowhere-zero integral chains and flows in bidirected graphs
复制标题
DOI：
10.1016/0095-8956(87)90032-3
复制
发表时间：
1987-08
期刊：
影响因子：
--
通讯作者：
A. Khelladi
中科院分区：
文献类型：
--
作者：
A. Khelladi
证明了无处零整链群的一般结果，并将其专门用于双向图中的流的情形。例如，证明了每一个4-连通的（分别是）3-连通且无平衡三角形）的双向图，该双向图具有至少一个不平衡回路和一个无零流，该双向图可以具有绝对值小于18的无零积分流（分别为. 30）。这改进了，对于这些类的图，Bouchet的216-流定理（J. Combin。Theory Ser.B34（1982），279-292）。我们也接近他的6流猜想证明它的一类3连通图。我们的方法受到Seymour的6流定理证明的启发（J. Combin. Theory Ser.B30（1981），130-136），并利用了符号图的新连通性性质。
General results on nowhere-zero integral chain groups are proved and then specialized to the case of flows in bidirected graphs. For instance, it is proved that every 4-connected (resp. 3-connected and balanced triangle free) bidirected graph which has at least an unbalanced circuit and a nowhere-zero flow can be provided with a nowhere-zero integral flow with absolute values less than 18 (resp. 30). This improves, for these classes of graphs, Bouchet's 216-flow theorem (J. Combin. Theory Ser. B34(1982), 279–292). We also approach his 6-flow conjecture by proving it for a class of 3-connected graphs. Our method is inspired by Seymour's proof of the 6-flow theorem (J. Combin. Theory Ser. B30(1981), 130–136), and makes use of new connectedness properties of signed graphs.