Full metadata
Title
On-line coloring of partial orders, circular arc graphs, and trees
Description
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. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs.
Date Created
2012
Contributors
- Smith, Matthew Earl (Author)
- Kierstead, Henry A (Thesis advisor)
- Colbourn, Charles (Committee member)
- Czygrinow, Andrzej (Committee member)
- Fishel, Susanna (Committee member)
- Hurlbert, Glenn (Committee member)
- Arizona State University (Publisher)
Topical Subject
Resource Type
Extent
vii, 109 p. : ill. (some col.)
Language
eng
Copyright Statement
In Copyright
Primary Member of
Peer-reviewed
No
Open Access
No
Handle
https://hdl.handle.net/2286/R.I.15995
Statement of Responsibility
by Matthew Earl Smith
Description Source
Retrieved on Oct. 11, 2013
Level of coding
full
Note
thesis
Partial requirement for: Ph.D., Arizona State University, 2012
bibliography
Includes bibliographical references (p. 105-109)
Field of study: Mathematics
System Created
- 2013-01-17 06:40:58
System Modified
- 2021-08-30 01:43:39
- 3 years 2 months ago
Additional Formats