2026-05-23T02:10:03Zhttps://keep.lib.asu.edu/oai/request

oai:keep.lib.asu.edu:node-1514292024-12-20T18:25:12Zoai_pmh:alloai_pmh:repo_items

151429 https://hdl.handle.net/2286/R.I.15995 http://rightsstatements.org/vocab/InC/1.0/ All Rights Reserved 2012 vii, 109 p. : ill. (some col.) Doctoral Dissertation Academic theses Text eng Smith, Matthew Earl Kierstead, Henry A Colbourn, Charles Czygrinow, Andrzej Fishel, Susanna Hurlbert, Glenn Arizona State University Partial requirement for: Ph.D., Arizona State University, 2012 Includes bibliographical references (p. 105-109) Field of study: Mathematics 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. Mathematics Circular arc graph first-fit On-line chain partition On-line graph coloring Partially ordered sets Tree Graph Theory On-line coloring of partial orders, circular arc graphs, and trees