## Files in this item

FilesDescriptionFormat

application/pdf

8823280.pdf (3MB)
(no description provided)PDF

## Description

 Title: Graph Labelings Author(s): Weaver, Margaret Lefevre Doctoral Committee Chair(s): West, Douglas B. Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics Computer Science Abstract: Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming non-crossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t (G) is the minimum number of pages in a book embedding of G. We present a general construction showing $t(K\sb{m,n}) \leq \lceil(m + 2n)/4\rceil$, which we conjecture to be optimal. We prove a result suggesting this is optimal for $m \geq 2n - 3$. For the most difficult case, $m = n$, we consider vertex permutations that are regular, i.e. place the vertices from each partite set into runs of equal size. Book embeddings with such orderings require $\lceil(7n - 2)/9\rceil$ pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.For k-tuples of integers $X = (x\sb1,x\sb2,\dots,x\sb{k})$ and $Y = (y\sb1,y\sb2,\dots,y\sb{k})$, let $\vert X - Y\vert$ = $\sum\sbsp{i = 1}{k}\vert x\sb{i} - y\sb{i}\vert$. The k-dimensional bandwidth problem for a graph G is to label the vertices $v\sb{i}$ of G with distinct k-tuples of integers $f (v\sb{i})$ so that the quantity max $\{\vert f(v\sb{i}) - f (v\sb{j}\vert{:}(v\sb{i},v\sb{j}) \in E(G)\}$ is minimized. We find bounds on the k-dimensional bandwidth of a graph in terms of other graph parameters and we find the bandwidth and k-dimensional bandwidth of several classes of graphs.For a given nontrivial graph H, an H-forbidden coloring of a graph G is an assignment of colors to the vertices of G so that G contains no monochromatic subgraph isomorphic to H. The H-forbidden chromatic number of G is the minimum number of colors in an H-forbidden coloring of G. An H-required coloring of G is an assignment of colors to the vertices of G such that every induced monochromatic subgraph of G is a subgraph of H. The H-required chromatic number of G is the minimum number of colors in an H-required coloring of G. We find triangle-free graphs with arbitrarily large star-required chromatic numbers and we seek an analogue to Brooks' Theorem for the $P\sb2$-required chromatic number, where $P\sb2$ is the path containing two vertices. We also find the generalized chromatic numbers of several classes of graphs, including the Cartesian product of cycles and the complete multipartite graphs, when the forbidden or required configurations are stars or paths. Issue Date: 1988 Type: Text Description: 93 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988. URI: http://hdl.handle.net/2142/71268 Other Identifier(s): (UMI)AAI8823280 Date Available in IDEALS: 2014-12-16 Date Deposited: 1988
﻿