A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist.
Download count: 0
- Partial requirement for: Ph.D., Arizona State University, 2012Note typethesis
- Includes bibliographical references (p. 105-109)Note typebibliography
- Field of study: Mathematics