Graph Structure, the Four Color Theorem, and Generalizations

点击翻译按钮获取中文摘要

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 research project is concerned with questions 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 underlying structure, to the design of efficient algorithms, to practical computations. For instance, one such question answered previously by the investigator settles a question of George Polya from 1913, solves a problem that baffled theoretical computer scientists for quarter of a century, and has applications in economics. The central theme of this project is graph structure theory and its applications to coloring, flows, and algorithms. More specifically, the investigator will study the structure of graphs pertaining to the graph minor inclusion and will use 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 will require the development of new tools in graph structure theory. Improved bounds will have immediate applications to the design of efficient algorithms.