图的整数流与循环流

The integer flow theory was initiated by Tutte as generalization of map coloring problems. Tutte made three outstanding flows conjectures: 3-flow conjecture, 4-flow conjecture and 5-flow conjecture, which are far-reaching generalizations of Grotzsch three coloring theorem, Four Color Theorem, Heawood Five Color Theorem on planar graphs, respectively. By allowing certain fraction values, Jaeger further extended the theory and problems to circular flows. .This proposed project would study Tutte’s flow conjectures from the essential edge connectivity aspect and the circular flow aspect. We propose to study 3-flow conjecture for highly essential edge-connected graphs, to approach 5-flow conjecture by showing all bridgeless graphs admit circular flow strictly less than 6, and to investigate circular flows of planar graphs. This project is devoted to make breakthroughs in the integer flow theory and problems, and it would develop new methods and techniques for eventually solving Tutte’s flow conjectures. Improvements and solutions of those problems would promote flow theory and the development of graph theory.

整数流理论由Tutte研究平面地图染色引入，已成为图论的经典研究方向。Tutte提出了一些著名的整数流猜想作为平面图染色定理，特别是四色定理，的推广和延伸。通过允许分数流值，Jaeger进一步将整数流扩展到循环流上，从而提出了更加广泛的问题和猜想。.本项目将从限制连通度和循环流逼近两个角度研究整数流猜想。在连通度方面，旨在对限制连通度较高的图证明三流猜想；在循环流方面，力争证明无桥图存在小于6流来进一步逼近五流猜想，以及通过研究平面图的循环流来理解一般图的循环流与整数流关系。本项目力争在流理论和相关问题上取得较大突破，在方法和技巧上得到创新，为解决整数流猜想提供新思路。这些问题的进展和解决将对整数流理论乃至图论学科的发展和完善具有重要意义。

整数流是图论中的经典研究方向，Tutte的流猜想是平面图四色定理的扩展和延伸。通过允许分数流值，Jaeger将整数流进一步扩展到循环流，提出了更加广泛的问题和猜想。本项目在整数流与循环流的研究方面取得了多个实质性进展，主要研究结果如下：(A)解决了Thomassen于1993年提出的关于近似平面图中三流存在性的公开问题，并且完整证明了环面图情形的Tutte三流猜想；(B)对Bouchet于1983年提出的符号图六流猜想取得突破并证明了整数11-流的存在性；(C)通过发展Tutte定向的新工具建立了循环流与定向之间新的关联，并利用这个新工具得到了高连通图循环流流值新的上界，扩展了经典的Jaeger四流定理；(D)通过运用Tutte定向的工具和发展新的图类合成运算，在k至少为12时，构造了无穷多的没有(2+2/k)-循环流的2k-边连通的第一类的(2k+1)-正则图，否定了Steffen的猜想，而且也延伸和推广了之前关于Jaeger循环流猜想的反例；(E)发展权函数的新方法给出了关于高连通平面图循环流的新结果，该结果的对偶版本证明了围长为10的平面图存在到5圈的同态，围长为16的平面图存在到7圈的同态；(F)完整刻画了3-边连通图的群连通性与群结构的关系，回答了Lai et al.(AMSE2011)和Husek et al.(JGT2020)提出的两个公开问题；(G)发展了符号图中整数流，循环流与群流的基本理论，证明了无桥符号图中循环流与模定向的等价性。