Skip navigation
Please use this identifier to cite or link to this item:
Title: On unavoidable graphs and tournaments
Authors: Kim, Ringi
Advisors: Seymour, Paul
Contributors: Applied and Computational Mathematics Department
Keywords: chromatic number
domination number
Subjects: Mathematics
Issue Date: 2016
Publisher: Princeton, NJ : Princeton University
Abstract: Ramsey's theorem asserts that every sufficiently large graph contains either a large complete graph or its complement as an induced subgraph. There are many variants of Ramsey's theorem. If we consider connected graphs, one knows that every large connected graph contains either a large complete graph, a large star or a long path as an induced subgraph. We call a theorem of this type a Ramsey-type theorem. In the first part of this thesis, we present new results on Ramsey-type theorems. In the second part of this thesis, we study tournaments with large chromatic number. The chromatic number of a tournament T is the minimum number of transitive subsets of V(T) covering all vertices of T. A class H of tournaments is heroic if every tournament containing none of the members of H has bounded chromatic number. In [3], Every heroic set with one tournament is explicitly characterized. In this thesis, we investigate heroic sets containing two tournaments. The third result is on tournaments with large domination number. The domination number of a tournament T is the minimum size of S⊆V(T) such that every vertex outside of S has an in-neighbor in S. A tournament T is a rebel if every tournament not containing T has bounded domination number. We investigate the following conjecture of Hehui Wu: every tournament is a rebel. We prove that the conjecture is false in general but every 2-colorable tournament is a rebel. Moreover we show that there is a rebel which is not 2-colorable.
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 
Kim_princeton_0181D_11849.pdf553.06 kBAdobe PDFView/Download

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