Covering and packing problems on graphs and hypergraphs
Christopher J. Stocker · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2011
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)| 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.