Covering and packing problems on graphs and hypergraphs

Packing;Domination;Acyclic Coloring

Stocker, Christopher J.

关键词: Packing;    Domination;    Acyclic Coloring;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/26316/Stocker_Christopher.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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 thevertex set of a graph by independent sets. We consider special cases of domination andcoloring 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)/2pack. 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 wegeneralize 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 withno connectivity restriction, better upper bounds exist for connected cubic graphs. InChapter 3, improving an upper bound of Kostochka and Stodolsky, we show that forn > 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 unionof any two color classes induces a forest. In Chapter 4 we show that every graph withmaximum degree at most 5 has an acyclic 7-coloring. We also show that every graphwith maximum degree at most r has an acyclic (1+⌊((r+1)^2)/4⌋)-coloring.