IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Covering and packing problems on graphs and hypergraphs

Show full item record

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

Files in this item

File Description Format
PDF 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
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 53
  • Downloads this Month: 6
  • Downloads Today: 0

Browse

My Account

Information

Access Key