论文标题
流量扩展和与应用程序的组连接
Flow Extensions and Group Connectivity with Applications
论文作者
论文摘要
我们研究了图的流量扩展，即，在入射到给定的顶点的边缘上的部分流程中预分配了部分流，并旨在扩展到整个图。这与Tutte的$ 3 $ Flow猜想（1972）密切相关，即每$ 4 $ - 边缘连接的图形都可以接收一个无处可及零3美元的$ 3 $ -Flow和$ \ mathbb {Z} _3 $ -Group Connectivity Connectivitivitive Connectivitivition Connignivitive conjecture（3GCC）Jaeger，Linial，Payan，Payan和Tarsi（1992年） $ \ mathbb {z} _3 $ - 连接。我们的主要结果表明，这些猜想等同于它们的自然流量扩展版本，并提出了一些应用。 $ 3 $ - 流案例提供了Kochol的结果（2001年）的替代证明，即Tutte的$ 3 $流量猜想相当于其对$ 5 $ - 边缘连接的图形的限制，并且由3GCC暗示。这也表明了一个新事实，即gr {Ö} tzsch的定理（无三角形的平面图为$ 3 $ - 可油）等同于其似乎较弱的腰围五个案例，grith $ 5 $ 5 $的平面图是$ 3 $ 3 $ - 可油。我们的方法允许验证3GCC的图表，其越过第一，实际上，这将减少为Richter，Thomassen和Younger（2017）证明的平面案例。还获得了其他等效版本的3GCC和相关部分结果。
We study the flow extension of graphs, i.e., pre-assigning a partial flow on the edges incident to a given vertex and aiming to extend to the entire graph. This is closely related to Tutte's $3$-flow conjecture(1972) that every $4$-edge-connected graph admits a nowhere-zero $3$-flow and a $\mathbb{Z}_3$-group connectivity conjecture(3GCC) of Jaeger, Linial, Payan, and Tarsi(1992) that every $5$-edge-connected graph $G$ is $\mathbb{Z}_3$-connected. Our main results show that these conjectures are equivalent to their natural flow extension versions and present some applications. The $3$-flow case gives an alternative proof of Kochol's result(2001) that Tutte's $3$-flow conjecture is equivalent to its restriction on $5$-edge-connected graphs and is implied by the 3GCC. It also shows a new fact that Gr{ö}tzsch's theorem (that triangle-free planar graphs are $3$-colorable) is equivalent to its seemly weaker girth five case that planar graphs of grith $5$ are $3$-colorable. Our methods allow to verify 3GCC for graphs with crossing number one, which is in fact reduced to the planar case proved by Richter, Thomassen and Younger(2017). Other equivalent versions of 3GCC and related partial results are obtained as well.
