Integer Flows and Tutte Orientations

整数流和 Tutte 方向

• 批准号: 1264800
• 负责人: Cun-Quan Zhang
• 金额: $ 12.8万
• 依托单位: West Virginia University Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-07-15 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1264800&HistoricalAwards=false
• 关键词: Integer; Flows; Tutte; Orientations

The map coloring problem is considered one of the major catalysts of the tremendous development of graph theory in its almost 300-year history. It is, thus, not surprising that graph coloring and its related problems have always been in the main line of graph theory research. It was observed by Tutte that the problem of the face-coloring of an embedded (planar) graph can be formulated in terms of integer flows of the graph. Since then the topic of integer flows has been one of the most attractive in graph theory. Grotzsch proved that every triangle free, loopless planar graph is 3-vertex-colorable. By flow/coloring duality, this is equivalent to the statement that every 4-edge-connected planar graph has a nowhere-zero 3-flow. The 3-flow Conjecture (by Tutte) asserts that this is still true without the assumption of planarity. Collaborating with his colleagues, the PI successfully proved that every 6-edge-connected graph admits nowhere-zero 3-flow. According to a result by Kochol that it suffices to prove 3-flow Conjecture for 5-edge-connected graphs. Thus our result is now only "one step away" from the final solution of this famous open problem. The PI will continue his research work in this direction. He proposes to extend those newly developed techniques for further studies in the theory of integer flows. Proposed projects will include not only the 3-flow Conjecture, but also 5-flow Conjecture, Tutte orientations, contractible configurations (group connectivity), flows for odd-edge-connected graph, circular flows and Circular Flow Conjecture, etc.The proposed work belongs to the area of graph theory and is closely related to computer science and operational research. A graph is an abstract mathematical notion used to model networks, such as communication systems, transportation networks or the Internet. Various graph coloring problems have been considered as effective models for radio channel assignment/distribution, and flow problems originally arise in optimizing traffic or network. This proposal is concerned with problems of structural nature. Why do some networks possess certain specific desirable properties, and others do not? Especially, when the reliability (connectivity) of a network decreases, certain flow patterns may disappear. A better understanding of such graphic properties will lead to designs of efficient algorithms, to practical computations.

图的着色问题被认为是图论在其近300年的历史中取得巨大发展的主要催化剂之一。因此，图的着色及其相关问题一直是图论研究的主线也就不足为奇了。Tutte观察到，嵌入式（平面）图的面着色问题可以用图的整数流来表示。从那时起，整数流的研究就成为图论中最具吸引力的课题之一。Grotzsch证明了每一个无三角形、无环路的平面图形都是3顶点可着色的。根据流/着色对偶性，这相当于每个4边连接的平面图形都有一个无处不在的3流。Tutte的三流猜想（3-flow Conjecture）断言，在没有平面性假设的情况下，这仍然是正确的。与他的同事合作，PI成功地证明了每一个6边连通图都不允许任何3流。根据Kochol的结果，足以证明5边连通图的3流猜想。因此，我们的结果现在离这个著名的开放问题的最终解只有“一步之遥”。PI将在这个方向上继续他的研究工作。他建议将这些新开发的技术扩展到整数流理论的进一步研究中。建议的项目不仅包括三流猜想，还包括五流猜想、Tutte取向、可收缩构型（群连通性）、奇边连通图流、循环流和循环流猜想等。建议的工作属于图论领域，与计算机科学和运筹学密切相关。图是一个抽象的数学概念，用于网络建模，如通信系统、交通网络或互联网。各种图形着色问题被认为是无线电信道分配/分配的有效模型，而流量问题最初出现在优化交通或网络中。这一建议涉及结构性问题。为什么有些网络具有某些特定的理想属性，而另一些则没有？特别是当网络的可靠性（连通性）降低时，某些流型可能会消失。更好地理解这种图形属性将导致设计有效的算法，进行实际计算。