Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp014x51hm497
 Title: On unavoidable graphs and tournaments Authors: Kim, Ringi Advisors: Seymour, Paul Contributors: Applied and Computational Mathematics Department Keywords: chromatic numberdomination numbergraphtournament 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. URI: http://arks.princeton.edu/ark:/88435/dsp014x51hm497 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 SizeFormat
Kim_princeton_0181D_11849.pdf553.06 kBAdobe PDF

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