Cliques, stable sets, and coloring in graphs with forbidden induced subgraphs

Abstract

The Gyarfás-Sumner conjecture [29, 42] states that for every tree T there is a function f such that for every graph G with no induced subgraph isomorphic to T the chromatic number of G is at most f(ω(G)), where ω(G) is its clique number. We prove this when T is a tree formed by joining two disjoint paths by an edge.

A class C of graphs has the EH-property if there is a δ > 0 such that every G∈C has a clique or stable set of size at least |V(G)|δ. The Erdős-Hajnal conjecture [21,22] states that for every graph H, the class of H-free graphs has the EH-property. One approach for proving this is showing that there exists an ε > 0 such that every G∈C contains two sets A, B with |A|, |B| ≥ ε|V(G)| and such that either no edges or all edges between the sets are present in G. We prove a conjecture of Liebenau and Pilipczuk [33], that for every tree T, the class of graphs containing neither T nor its complement as an induced subgraph has this property, and thus has the EH-property. This generalizes several previous results [4,7,33,34]. We consider variants obtained by requiring that G is sparse, or A, B have polynomial instead of linear size, or the density between A and B is bounded, or G contains few copies of H. We prove a conjecture of Conlon, Fox and Sudakov [18] for almost bipartite graphs. Our results imply an improved bound for the Erdős-Hajnal conjecture for excluding a five-cycle, the simplest open case.

The strong perfect graph theorem [11] contains a decomposition theorem, and even though perfect graphs can be colored in polynomial time [28], no combinatorial algorithm for this is known. One obstacle for such an algorithm are "skew partitions", which arise from induced subgraphs isomorphic to line graphs. Generalizations of line graphs, so-called orthogonal strip systems, yield particularly bad skew partitions. We prove that in a perfect graph, under mild assumptions, the number of pairwise orthogonal strip systems is bounded by twice the clique number.