Files in this item

FilesDescriptionFormat

application/pdf

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

Description

Title:Structural and extremal results in graph theory
Author(s):LeSaulnier, Timothy
Advisor(s):West, Douglas B.
Contributor(s):West, Douglas B.; Furedi, Zoltan; Ferrara, Michael J.
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Doctoral
Subject(s):immersion
immersion-closed
rainbow Ramsey theory
rainbow domination
rainbow edge-chromatic number
rainbow decomposition
acquisition
acquisition-extremal
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:thesis
URI:http://hdl.handle.net/2142/29742
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

  • Total Downloads: 355
  • Downloads this Month: 5
  • Downloads Today: 0