Excluding substructures in graphs

主要研究者：玛丽亚·丘德诺夫斯基 提案编号：DMS -0758364机构：哥伦比亚大学题目：排除图中的子结构该提案涉及图论中的三个问题：完美图的结构和着色，Hadwiger猜想和Erdos Hajnal猜想。这三个问题都是图论领域中著名的基本问题。所有这三个问题都涉及排除某些子结构的图，目标是研究这些图的结构，希望理解这种结构将揭示问题的解决方案。传统上，结构方法被用来解决前两个问题;另一方面，从结构的角度来处理最后一个问题是一个相对较新的想法，从最近的一些结果来看， 第一个提出的问题是研究完美图的结构，目标是找到一个多项式时间的组合着色算法。第二个是Hadwiger的一个长期存在的猜想，该猜想指出，对于每个整数p，每个没有大小为p+1的团子的无环图都是p-可着色的。最后，Erdos Hajnal猜想指出，在没有导出子图同构于给定图H的图G中，存在一个团或一个稳定集，其大小是G的顶点数的多项式. (Thus 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.)