Skip navigation
Please use this identifier to cite or link to this item:
Title: Cliques, stable sets, and coloring in graphs with forbidden induced subgraphs
Authors: Spirkl, Sophie Theresa
Advisors: Chudnovsky, Maria
Seymour, Paul
Contributors: Applied and Computational Mathematics Department
Keywords: coloring
graph theory
induced subgraph
Subjects: Mathematics
Issue Date: 2018
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Spirkl_princeton_0181D_12546.pdf874.52 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.