偶子图覆盖、整数流与群连通及路分解问题研究

Even subgraph cover of graphs, integer flow and group connectivity and path decomposition of graphs are at the core of the study of structural graph theory，these problems also are challengable in the study of graph theory . The item mainly concerns about the shortest even subgraph cover conjecture, 3-flow conjecture and Abelian group of order 3 connectivity conjecture and Gallai's conjecture about path decomposition of simple connected graphs. We also concern about some related conjectures or problems (for example, Berge-Fulkerson conjecture, Fan-Raspaud conjecture, Fano coloring problems, the Abelian group of order k(>3) connectivity problems, and problems about (faulted vertex- or edge-) forwarding index). These conjectures and problems are not only related but also interactive. We want to give a new upper bound of shortest even subgraph cover of bridgeless cubic graphs, show that Berge-Fulkerson conjecture (Fan-Raspaud conjecture and Fano 4 lines coloring conjecture, an equivalent conjecture of Fan-Raspaud conjecture) is true for some cubic graphs with edge-chromatic number 4 (called snarks), give a proof of the 3 flow conjecture, make an important improvement on Gallai's conjecture and give the (faulted vertex- or edge-)forwarding index of some important networks. The proofs of these conjectures or making important improvements on these conjectures or problems will improve the development of graph theory.

图的偶子图覆盖、整数流及群连通和图的路分解等问题都是结构图论中的核心问题，也是图论中富有挑战性的课题。本项目紧紧围绕最短偶子图覆盖猜想、3流猜想及3阶交换群连通猜想、简单连通图的路分解猜想（Gallai猜想）开展研究，研究内容兼顾和这些猜想密切相关的一些猜想和问题（如Berge-Fulkerson猜想、Fan-Raspaud猜想、Fano染色问题、高阶交换群的群连通问题及有较强应用背景的（容错点或边）转发指数问题）。这些研究内容既相互交叉，又相互促进。本项目希望给出3正则图最短偶子图覆盖长的新上界，证明Berge-Fulkerson猜想（或Fan-Raspaud猜想）对某些3正则非3边染色图(snark)成立，解决3流猜想，在Gallai的图的路分解猜想上取得较大进展，求出一些重要网络的（容错点或边）转发指数。这些猜想或问题的解决或取得大的进展对图论理论的完善和发展都具有重要意义。

本项目主要围绕结构图论中几个核心问题，如图的偶子图覆盖、整数流及群连通和图的分解问题开展研究。主要研究内容包括最短圈覆盖猜想、整数流猜想、图的分解猜想、Berge-Fulkerson猜想和若干图论应用问题。这些研究内容既相互交叉，又相互促进。本项目围绕上述问题取得主要成果如下：证明了Berge-Fulkerson猜想对几乎Kotzig图（一类特殊snark）成立，研究了匹配覆盖和双圈覆盖之间的关系；研究了Jaeger的模（2p+1）可定向性猜想，完全解决了模（2p+1）可定向性质的Ramsey型问题；证明了一类6环边连通图存在非零5流，在5流猜想上取得了进展；在图的分解问题上从整体性质入手，给出了若干个奇圈交于一点的扇形图的图兰数及其极图；解决了一个图分解为扇形图及边的分解问题；给出了若干特殊图类broom数和pebbling数（两个具有应用背景图论参数）。这些猜想或问题的解决或取得大的进展对图论理论的完善和发展都具有重要意义。