# Covering and packing problems on graphs and hypergraphs

Bookmark or cite this item: http://hdl.handle.net/2142/26316

## Files in this item

File Description Format
Stocker_Christopher.pdf (853KB) (no description provided) PDF
 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 Urbana-Champaign 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 n-vertex 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 n-vertex 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 n-vertex 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 n-vertex 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 7-coloring. We also show that every graph with maximum degree at most r has an acyclic (1+⌊((r+1)^2)/4⌋)-coloring. Issue Date: 2011-08-26 URI: http://hdl.handle.net/2142/26316 Rights Information: Copyright 2011 Christopher J. Stocker Date Available in IDEALS: 2013-08-27 Date Deposited: 2011-08