Extremal problems in graph theory
Show full item record
Files in this item
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 UrbanaChampaign 
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 noncontractible chordless cycle C of G, there is a 3coloring 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 edgecoloring of G such that the color sets at vertices of G are pairwise distinct. A graph G has a setbalanced kedgecoloring 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 setbalanced kedgecoloring whenever G is a member of various classes of graphs.
The spotchromatic 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{k1}.$ 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 ksubsets 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: 
20120301 
Items in IDEALS are protected by copyright, with all rights reserved, unless otherwise indicated.
This item appears in the following Collection(s)
Show full item record
Item Statistics
 Total Downloads: 221
 Downloads this Month: 6
 Downloads Today: 0