Collaborative Research: cliques, stable sets and approximate structure

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

This proposal deals with a number of problems in graph theory related to the study of graphs with certain induced subgraphs excluded. The first problem is the famous Erdos-Hajnal conjecture, and its tournament version due to Alon, Pach and Solymosi. Following recent results, the PI plans to combine structural methods with techniques related to Szemeredi's regularity lemma to make further progress. The second set of problems is a conjecture of Gyarfas and Sumner, and questions related to chi-boundedness. In particular, the PI plans to study tournament versions of some of the related classical questions. The last proposed research direction is the general question of the structure of graphs with forbidden induced subgraphs, where particular emphasis is placed on perfect graphs. The PI's have extensive experience in the area, in combination with recent ideas of "extreme decompositions'', is likely to lead to new results.This proposal deals with three problems in graphs theory. All three are about graphs with certain forbidden substructures (called "induced subgraphs") excluded; and different aspects of graph behavior are studied in each of the problems. The first two questions considered in the proposal are known conjectures in the field; their solution, or any progress on them, will be of interest to many researchers. The last research direction is more of a "theory building" question, where a general approach, that can be used for a large number of problems, will be developed.