IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Extremal problems in graph theory

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/29956

Files in this item

File Description Format
PDF Hartman_Christopher.pdf (3MB) (no description provided) PDF
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
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 221
  • Downloads this Month: 6
  • Downloads Today: 0

Browse

My Account

Information

Access Key