Collaborative Research: cliques, stable sets and approximate structure

本文讨论了图论中与排除某些诱导子图的图的研究有关的若干问题。第一个问题是著名的Erdos-Hajnal猜想，它的锦标赛版本是由阿隆、帕奇和索利莫西提出的。根据最近的结果，PI计划将结构方法与Szemeredi正则引理相关的技术结合起来，以取得进一步的进展。第二组问题是Gyarfas和Sumner的一个猜想，以及与chi-bounded有关的问题。特别是，PI计划研究一些相关经典问题的锦标赛版本。最后提出的研究方向是具有禁止诱导子图的图的一般结构问题，其中特别强调了完美图。PI在该领域拥有丰富的经验，结合最近的“极端分解”思想，可能会产生新的结果。本文讨论图论中的三个问题。这三种图都是关于排除某些禁止子结构（称为“诱导子图”）的图；在每个问题中都研究了图行为的不同方面。提案中考虑的前两个问题是该领域已知的猜想；他们的解决方案或任何进展都将引起许多研究人员的兴趣。最后一个研究方向更多的是一个“理论建设”问题，在这个问题上，将开发一个通用的方法，可以用于大量的问题。

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.