Files in this item



application/pdfLeSaulnier_Timothy.pdf (778kB)
(no description provided)PDF


Title:Structural and extremal results in graph theory
Author(s):LeSaulnier, Timothy
Director of Research:West, Douglas B.
Doctoral Committee Member(s):West, Douglas B.; Furedi, Zoltan; Ferrara, Michael J.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
rainbow Ramsey theory
rainbow domination
rainbow edge-chromatic number
rainbow decomposition
Abstract:An H-immersion is a model of a graph H in a larger graph G. Vertices of H are represented by distinct "branch" vertices in G, while edges of H are represented by edge-disjoint walks in G joining branch vertices. By the recently proved Nash-Williams Immersion Conjecture, any immersion-closed family is characterized by forbidding the presence of H-immersions for a finite number of graphs H. We off er descriptions of some immersion-closed families along with their forbidden immersion characterizations. Our principal results in this area are a characterization of graphs with no K_{2,3}-immersion, and a characterization of graphs with neither a K_{2,3}-immersion nor a K_4-immersion. We study of the maximum number of edges in an n-vertex graph with no K_t-immersion. For t≤7, we determine this maximum value. When 5≤t≤7, we characterize the graphs with no K_t-immersion having the most edges. Given an edge-colored graph, a rainbow subgraph is a subgraph whose edges have distinct colors. We show that if the edges of a graph G are colored so that at least k colors appear at each vertex, then G contains a rainbow matching of size floor(k/2). We consider the rainbow edge-chromatic number of an edge-colored graph, \chi'_r(G), which we define to be the minimum number of rainbow matchings partitioning the edge set of G. A d-tolerant edge-colored graph is one that contains no monochromatic star with d + 1 edges. We off er examples of d-tolerant n-vertex edge-colored graphs G for which \chi'_r(G)≥d/2 (n-1) and prove that \chi'_r(G)
Issue Date:2012-02-06
Genre:Dissertation / Thesis
Rights Information:Some material copyright 2010 Timothy LeSaulnier.
Date Available in IDEALS:2012-02-06
Date Deposited:2011-12

This item appears in the following Collection(s)

Item Statistics