3-流猜想，Fulkerson-覆盖及相关问题

The map coloring problem is considered one of the most important catalysts of the tremendous development of graph theory. In the 1940s and 1950s, Tutte observed that the problem of the face-coloring of a planar graph can be formulated in terms of integer flows of the graph, as well as in terms of its cycle covers. Since then the topics of integer flows and cycle covers have become two of the major research fields in graph theory.. In this project, we mainly study 3-flow conjecture, Fulkerson-cover and related problems.. In terms of 3-flow conjecture, we intend to prove that 3-flow conjecture holds on some special 5-edge-connected graphs; In the extreme value of even factor, we intend to give a better lower bound of the connected even factors in a supereulerian graph; And in the field of Fulkerson-conjecture, we intend to prove that Fulkerson-conjecture holds on some special graphs.

在图论的发展历史中，地图着色问题被认为是一个非常重要的催化剂。在二十世纪四五十年代，Tutte 发现平面图的面着色问题既可以转化为平面图的整数流问题，又可以转化为平面图的圈覆盖问题。自此，整数流问题与圈覆盖问题成为图论的两大研究领域。. 本课题主要对3-流猜想，Fulkerson-覆盖及相关问题进行深入的研究。. 在3-流猜想方面，本课题拟证明3-流猜想在某些特殊的5-边连通的图上成立；在连通偶因子极值方面，本课题拟给出超欧拉图中连通偶因子的一个比较好的下界；在Fulkerson-覆盖方面，本课题拟证明Fulkerson-猜想在某些特殊的图类上成立。

在图论的发展历史中，地图着色问题被认为是一个非常重要的催化剂。在二十世纪四五十年代，Tutte发现平面图的面着色问题既可以转化为平面图的整数流问题，又可以转化为平面图的圈覆盖问题。自此，整数流问题与圈覆盖问题成为图论的两大研究领域。. 在已有工作的基础上，本项目主要拟对3-流猜想，Fulkerson-覆盖及相关问题进行深入的研究。. 在Fulkerson-覆盖方面，我们证明Fulkerson-猜想在某类hypohamiltonian图和某些没有割边的三正则图上成立。在连通偶因子极值方面，我们证明了Lai和Yan在文章Supereulerian graphs and matchings中提出的猜想，并且在证明Lai和Yan提出的猜想的过程中，我们考虑了α’(G)≤5这一情形，我们发现如果α’(G)≤5，则Gallai猜想（连通图中所有的最长路有一个公共点）是成立的，同时，我们证明Gallai猜想的最小反例含有12个顶点。在研究超欧拉图的过程中，我们发现了一类非常有趣的图-轮图。我们证明对于每一个含有m条边并且不含有轮图W_{2k}作为子图的图，都存在一个至少含有m/2+c(k)m^{2k-1/3k-1}logm条边的二部子图。在研究过程中，我们做了代数图论的一些研究。我们提出了一种新的基于距离的分子拓扑指数：迂回哈瑞指数（Detour-Harary index）。我们通过图的变换方法分别得到了单圈图、双圈图和仙人掌图该指数的最大值及所有对应的极图。