Files in this item
Files  Description  Format 

application/pdf LeSaulnier_Timothy.pdf (778kB)  (no description provided) 
Description
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 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  immersion
immersionclosed rainbow Ramsey theory rainbow domination rainbow edgechromatic number rainbow decomposition acquisition acquisitionextremal 
Abstract:  An Himmersion 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 edgedisjoint walks
in G joining branch vertices. By the recently proved NashWilliams Immersion Conjecture,
any immersionclosed family is characterized by forbidding the presence of Himmersions for
a finite number of graphs H. We off er descriptions of some immersionclosed 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_4immersion. We study of the maximum number of edges
in an nvertex graph with no K_timmersion. For t≤7, we determine this maximum value.
When 5≤t≤7, we characterize the graphs with no K_timmersion having the most edges.
Given an edgecolored 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
edgechromatic number of an edgecolored graph,
\chi'_r(G), which we define to be the minimum
number of rainbow matchings partitioning the edge set of G. A dtolerant edgecolored
graph is one that contains no monochromatic star with d + 1 edges. We off er examples
of dtolerant nvertex edgecolored graphs G for which \chi'_r(G)≥d/2 (n1) and prove that
\chi'_r(G) 
Issue Date:  20120206 
Genre:  thesis 
URI:  http://hdl.handle.net/2142/29742 
Rights Information:  Some material copyright 2010 Timothy LeSaulnier. 
Date Available in IDEALS:  20120206 
Date Deposited:  201112 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics