图论中的整数流与圆流

In this project, we investigate integer flow and circular flow problems on graphs. Tutte's 3-Flow Conjecture and 5-Flow Conjecture are two kernel problems of graph theory. Jeager generalized those two conjectures to a stronger one, known as the Circular Flow Conjecture. Considering the hardness of the problems, Jeager also proposed the weaker versions of the Conjectures, called weak 3-Flow Conjecture and weak Circular Flow Conjecture. Howerver even the two weaker conjectures were still remained open in a long dormant period. In 2011, Carsten Thomassen (member of the Royal Danish Academy of Sciences and letters) finally solved the weak 3-Flow Conjecture and weak Circular Flow Conjecture. Later in cooperation with Laszlo Miklos Lovasz and Carsten Thomassen, my PhD advisor professor Chunquan Zhang and I improved those two results, and in cooperation with Dong Ye and Wenan Zang, we generalized Thomassen’s weak 3-Flow Theorem to signed graphs. In the future we shall continue study the problems related to integer flows and circular flow, focusing on 3-flow probem on graphs and signed graph, and try to solve 3-Flow Conjecture completely.

本项目旨在研究图论中的关于流理论方面的内容，包括整数流和圆流相关问题。由Tutte提出的3-流猜想和5-流猜想是图论中的两个核心难题。Jeager进一步将它们推广为统一的圆流猜想。同时考虑到问题的难度，Jeager还提出了它们的弱化版本: 弱3-流猜想和弱圆流猜想。即便如此，这两个弱化的猜想长期悬而未决。直到2011年，弱3-流猜想和弱圆流猜想才最终被丹麦科学院院士Carsten Thomassen解决。随后本项目申请人和博士导师张存铨教授在与Laszlo Miklos Lovasz及Carsten Thomassen的合作中，进一步改进了这两个结果，并在与Dong Ye及Wenan Zang的合作中将Thomassen的弱3-流定理推广到符号图上。本项目将继续研究关于图的整数流和圆流的相关研究, 重点是图与符号图中的3-流问题，拟完全解决3-流猜。

本项目研究图论中的流理论及其相关问题，主要关注Tutte的3-流猜想和5-流猜想，以及Jaeger的圆流猜想。我们推广了Jeager于1984年给出的圆流与mod定向之间的等价关系，证明了一个图的流值小于(2+1/p)等价于该图有mod(2p+1)定向，并利用该关系证明了8-边连通都有小于3的流；给出了圆流猜想的两类反例，即在p≥3和p≥5的时候，分别有4p和(4p+1)-边连通的图是没有mod(2p+1)定向的，这个结果否定了圆流猜想（除了p=1,2的特例外）；利用流理论的相关结果，我们证明了1-2猜想（1-2-3猜想的加强版）对高边连通图（相对图的染色数）是成立的，并对二部图是否满足1-2猜想给出了一个充要条件；证明了4-边连通图都满足1-2-3猜想；给出了2-连通3-正则符号图的最小圈覆盖的一个比例上界。总共发表SCI检索期刊论文8篇。