2026-05-23T00:21:28Zhttps://keep.lib.asu.edu/oai/request

oai:keep.lib.asu.edu:node-1500652024-12-20T18:25:12Zoai_pmh:alloai_pmh:repo_items

150065 https://hdl.handle.net/2286/R.I.9361 http://rightsstatements.org/vocab/InC/1.0/ All Rights Reserved 2011 v, 61 p. : ill Doctoral Dissertation Academic theses Text eng Bland, Adam K Kierstead, Henry A Czygrinow, Andrzej M Hurlbert, Glenn H. Barcelo, Helene Aen, Arunabha Arizona State University Partial requirement for: Ph.D., Arizona State University, 2011 Includes bibliographical references (p Field of study: Mathematics Let T be a tournament with edges colored with any number of colors. A rainbow triangle is a 3-colored 3-cycle. A monochromatic sink of T is a vertex which can be reached along a monochromatic path by every other vertex of T. In 1982, Sands, Sauer, and Woodrow asked if T has no rainbow triangles, then does T have a monochromatic sink? I answer yes in the following five scenarios: when all 4-cycles are monochromatic, all 4-semi-cycles are near-monochromatic, all 5-semi-cycles are near-monochromatic, all back-paths of an ordering of the vertices are vertex disjoint, and for any vertex in an ordering of the vertices, its back edges are all colored the same. I provide conjectures related to these results that ask if the result is also true for larger cycles and semi-cycles. A ruling class is a set of vertices in T so that every other vertex of T can reach a vertex of the ruling class along a monochromatic path. Every tournament contains a ruling class, although the ruling class may have a trivial size of the order of T. Sands, Sauer, and Woodrow asked (again in 1982) about the minimum size of ruling classes in T. In particular, in a 3-colored tournament, must there be a ruling class of size 3? I answer yes when it is required that all 2-colored cycles have an edge xy so that y has a monochromatic path to x. I conjecture that there is a ruling class of size 3 if there are no rainbow triangles in T. Finally, I present the new topic of alpha-step-chromatic sinks along with related results. I show that for certain values of alpha, a tournament is not guaranteed to have an alpha-step-chromatic sink. In fact, similar to the previous results in this thesis, alpha-step-chromatic sinks can only be demonstrated when additional restrictions are put on the coloring of the tournament's edges, such as excluding rainbow triangles. However, when proving the existence of alpha-step-chromatic sinks, it is only necessary to exclude special types of rainbow triangles. Mathematics Tournaments Tournaments (Graph theory) Reachability in K-colored tournaments