Excluding substructures in graphs

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

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.)