Please use this identifier to cite or link to this item:

`http://arks.princeton.edu/ark:/88435/dsp01zw12z7994`

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

URI: | http://arks.princeton.edu/ark:/88435/dsp01zw12z7994 |

Alternate format: | The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu |

Type of Material: | Academic dissertations (Ph.D.) |

Language: | en |

Appears in Collections: | Applied and Computational Mathematics |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

Spirkl_princeton_0181D_12546.pdf | 874.52 kB | Adobe PDF | View/Download |

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