Graph Structure, the Four Color Theorem, and Generalizations

这项工作属于图论领域，与理论计算机科学和数学编程(运筹学)密切相关。图是一种抽象的数学概念，用于对电话网络、交通网络或互联网等网络进行建模。在对这类网络的研究中出现了各种问题，而本研究项目涉及的是结构性问题。为什么有些网络拥有某些特定的理想属性，而其他网络则没有？一个令人满意的答案可以有很多应用，从更好地理解底层结构，到设计有效的算法，再到实际的计算。例如，研究人员之前回答的一个这样的问题解决了1913年乔治·波利亚的一个问题，解决了一个困扰理论计算机科学家25年的问题，并在经济学中有应用。这个项目的中心主题是图结构理论及其在着色、流和算法中的应用。更具体地说，调查者将研究与图的次要包含有关的图的结构，并将使用这些结果来攻击流和着色问题，以及刻画“Pfaffian图”的问题。Pfaffian图之所以引起人们的兴趣，是因为它们允许高效地计算完美匹配，并且其丰富的理论与其他领域相关。这项研究需要在图结构理论中开发新的工具。改进的边界将立即应用于高效算法的设计。

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.