Files in this item
Files  Description  Format 

application/pdf Stocker_Christopher.pdf (853kB)  (no description provided) 
Description
Title:  Covering and packing problems on graphs and hypergraphs 
Author(s):  Stocker, Christopher J. 
Director of Research:  Kostochka, Alexandr V. 
Doctoral Committee Chair(s):  West, Douglas B. 
Doctoral Committee Member(s):  Kostochka, Alexandr V.; Furedi, Zoltan; Balogh, József 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Packing
Domination Acyclic Coloring 
Abstract:  In this thesis we consider several extremal problems for graphs and hypergraphs: packing, domination, and coloring. Graph packing problems have many applications to areas such as scheduling and partitioning. We consider a generalized version of the packing problem for hypergraphs. There are many instances where one may wish to cover the vertices or edges of a graph. A dominating set may be thought of as a covering of the vertex set of a graph by stars. Similarly a proper coloring may be thought of as a covering of the vertex set of a graph by independent sets. We consider special cases of domination and coloring on graphs. Two nvertex hypergraphs G and H pack if there is a bijection f : V (G) → V (H) such that for every edge e ∈ E(G), the set {f(v) : v ∈ e} is not an edge in H. Sauer and Spencer showed that any two nvertex graphs G and H with E(G) + E(H) < (3n−2)/2 pack. Bollob´as and Eldridge proved that, with 7 exceptions, if graphs G and H contain no spanning star and E(G) + E(H) ≤ 2n − 3, then G and H pack. In Chapter 2 we generalize the Bollob´as – Eldridge result to hypergraphs containing no edges of size 0, 1, n − 1, or n. As a corollary we get a hypergraph version of the Sauer – Spencer result. In 1996 Reed proved that for every nvertex graph G with minimum degree 3 the domination number is at most 3n/8 . While this result is sharp for cubic graphs with no connectivity restriction, better upper bounds exist for connected cubic graphs. In Chapter 3, improving an upper bound of Kostochka and Stodolsky, we show that for n > 8 the domination number of every nvertex connected cubic graph is at most ⌊5n/14⌋. This bound is sharp for 8 < n ≤ 18 and nears the best known lower bound of 7n/20 . An acyclic coloring is a proper coloring with the additional property that the union of any two color classes induces a forest. In Chapter 4 we show that every graph with maximum degree at most 5 has an acyclic 7coloring. We also show that every graph with maximum degree at most r has an acyclic (1+⌊((r+1)^2)/4⌋)coloring. 
Issue Date:  20110826 
URI:  http://hdl.handle.net/2142/26316 
Rights Information:  Copyright 2011 Christopher J. Stocker 
Date Available in IDEALS:  20130827 
Date Deposited:  201108 
This item appears in the following Collection(s)

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