Graph Structure, Coloring, Flows and Algorithms

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

The central theme of this proposal is graph structure theory and its applications to coloring, flows and algorithms. More specifically, the principal investigator studies the structure of graphs pertaining to the graph minor inclusion and its relatives, such as the directed minor and matching minor relations, and uses those results to attack flow and coloring problems, as well as the problem of characterizing ``Pfaffian graphs". Pfaffian graphs are of interest because they allow efficient computation of perfect matchings, and their rich theory is related to other areas. This research requires the development of new tools in graph structure theory. In particular, the PI proposes an in-depth study of the notion of ``society", originally introduced by Robertson and Seymour. Applications of the theory range from theoretical (the flow conjectures, the double cycle conjecture) to more algorithmic (coloring graphs on surfaces and graphs belonging to a proper minor-closed family). An important method employed in the proof of the Four-Color Theorem is the technique of ``reducibility". While it is essential for the proof, there is almost no associated theory. The PI attempts to develop such a theory for the Four-Color Theorem, for the 5-Flow Conjecture and for the Cycle Double Cover Conjecture. A successful theory of reducibility (if it exists) will hopefully lead to a computer-free proof of the Four-Color Theorem and to proofs of the 5-Flow and Cycle Double Cover Conjectures. This work falls within the area of graph theory, and is closely related to theoretical computer science and mathematical programming (operations research). A graph is an abstract mathematical notion used to model networks, such as telephone networks, transportation networks or the Internet. Various problems arise in the study of such networks, and this proposal is concerned with problems of structural nature. Why do some networks possess certain specific desirable properties, and others do not? A satisfactory answer can have many applications, ranging from better understanding of the undelying structure, to the design of efficient algorithms, to practical computations. For instance, one such question answered earlier by the PI settles a question of Georgia Polya from 1913, it also solves a different problem that baffled theoretical computer scientists for quarter of a century, and has applications in economics.