Excluding substructures in graphs

摘要主要研究者：Chudnovsky， Maria提案号：DMS - 0758364机构：哥伦比亚大学题目：排除图中的子结构该提案涉及图论中的三个问题：完美图的结构和着色、Hadwiger猜想和Erdos Hajnal猜想。这三个问题都是图论领域中众所周知的基本问题。这三个问题都处理排除了特定子结构的图，目标是研究这种图的结构，希望理解这种结构将揭示问题的解决方案。传统上，结构性方法被用来解决前两个问题；另一方面，从结构的角度来解决最后一个问题是一个相对较新的想法，鉴于最近的一些结果，它似乎很有希望。第一个问题是研究完美图的结构，目标是找到一个多项式时间组合着色算法。第二个是Hadwiger的一个长期存在的猜想，即对于每一个整数p，每一个没有大小为p+1的小团的无循环图都是p色的。最后，Erdos Hajnal猜想断言，在没有诱导子图同构于给定图H的图G中，在G的顶点数中存在团或大小多项式的稳定集合（因此，G没有诱导子图同构于H的事实使得G从Ramsey理论的角度来看与随机图“非常不同”）。

ABSTRACTPrincipal Investigator: Chudnovsky, Maria Proposal Number: DMS - 0758364Institution: Columbia UniversityTitle: Excluding substructures in graphsThe proposal deals with three problems in graph theory: structure and coloring of perfect graphs, Hadwiger's conjecture, and the Erdos Hajnal conjecture. All three are well-known fundamental problems in the field of graph theory. All three problems deal with graphs with certain substructures excluded, and the goal is to investigate the structure of such graphs, with the hope that understanding this structure will uncover the solution to the problems. Structural approaches have been traditionally used to attack the first two problems; on the other hand, approaching the last problem from the point of view of structure is a relatively new idea, which in view of some resent results, seems quite promising.The first proposed question is to study the structure of perfect graphs, with the goal of finding a polynomial time combinatorial coloring algorithm. The second is a long standing conjecture of Hadwiger that states that for every integer p, every loopless graph with no clique minor of size p+1 is p-colorable. Finally, the Erdos Hajnal conjecture asserts that in a graph G with no induced subgraph isomorphic to a given graph H, there exists either a clique or a stable set of size polynomial in the number of vertices of G. (Thus, the fact that G has no induced subgraph isomorphicto H makes G ``very different'' from a random graph from the point of view of Ramsey theory.)