Integer Flows and 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.