Graph Structure, the Four Color Theorem, and Generalizations

这项工作属于图论领域，与理论计算机科学和数学规划（运筹学）密切相关。图是一个抽象的数学概念，用于对网络（如电话网络、交通网络或Internet）进行建模。这种网络的研究中出现了各种各样的问题，本研究项目涉及的是结构性质的问题。为什么有些网络具有某些特定的理想属性，而另一些则没有？一个令人满意的答案可以有很多应用，从对底层结构的更好理解，到有效算法的设计，再到实际计算。例如，研究者先前回答的一个这样的问题解决了乔治·波利亚1913年提出的一个问题，解决了一个困扰理论计算机科学家四分之一个世纪的问题，并在经济学中有应用。这个项目的中心主题是图结构理论及其在着色、流和算法中的应用。更具体地说，研究者将研究与图次要包含有关的图的结构，并将使用这些结果来解决流和着色问题，以及表征“法非图”的问题。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.