## Files in this item

FilesDescriptionFormat

application/pdf

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

## Description

 Title: Extremal problems in graph theory Author(s): Hartman, Christopher M. Director of Research: West, Douglas B. Doctoral Committee Chair(s): Weichsel, Paul M. Doctoral Committee Member(s): Francis, George K.; Edelsbrunner, Herbert Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): graph theory Abstract: We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\ge{3\over4}k\sp2\pm k,$ depending on whether k is even or odd. The path chromatic number $\chi\sb{P}(G)$ of a graph G is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of paths. We characterize cartesian products of cycles with path chromatic number 2. We show that if G is a toroidal graph, then for any non-contractible chordless cycle C of G, there is a 3-coloring of the vertices of G so that each color class except one induces a disjoint union of paths, while the third color class induces a disjoint union of paths and the cycle C. The path list chromatic number of a graph, $\\chi\sb{P}(G),$ is the minimum k for which, given any assignment of lists of size k to each vertex, G can be colored by assigning each vertex a color from its list so that each color class induces a disjoint union of paths. We prove that $\\chi\sb{P}(G)\le3.$ The observability of a graph G is least number of colors in a proper edge-coloring of G such that the color sets at vertices of G are pairwise distinct. A graph G has a set-balanced k-edge-coloring if the edges of G can be properly colored with k colors so that, for each degree, the color sets at vertices of that degree occur with multiplicities differing by at most one. We determine the values of k such that G has a set-balanced k-edge-coloring whenever G is a member of various classes of graphs. The spot-chromatic number of a graph, $\chi\sb{S}(G),$ is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of cliques. We show that $\chi\sb{S}(K\sb{mt}\ \square\ K\sb{nt})\le{mnt\over m+n}+2\min(m,n)$ whenever $m+n$ divides t. Let ${\cal G}\sb0=\{K\sb1\}.$ For $k\ge1,$ the family ${\cal G}\sb{k}$ of twisted hypercubes of dimension k is the set of graphs constructible by adding a matching joining two graphs in ${\cal G}\sb{k-1}.$ We construct a family of twisted hypercubes of small diameter. We prove that the order of growth of the minimum diameter among twisted hypercubes of dimension k is $\Theta(k$/lg k). The domination number $\gamma(G)$ of a graph G is the minimum size of a set S such that every vertex of G is in S or is adjacent to some vertex in S. The Kneser graph $K(n, k)$ has as vertices the k-subsets of $\lbrack n\rbrack.$ We determine $\gamma(K(n,k))$ when $n\ge{3\over4}k\sp2\pm k$ depending on the parity of k. Issue Date: 1997 Genre: Dissertation / Thesis Type: Text Language: English URI: http://hdl.handle.net/2142/29956 Rights Information: Copyright 1997 Christopher M. Hartman Date Available in IDEALS: 2012-03-01
﻿