Extremal problems in graph theory

Hartman, Christopher M.

Permalink

https://hdl.handle.net/2142/29956 Copy

Description

Title

Extremal problems in graph theory

Author(s)

Hartman, Christopher M.

Issue Date

1997

Director of Research (if dissertation) or Advisor (if thesis)

West, Douglas B.

Doctoral Committee Chair(s)

Weichsel, Paul M.

Committee Member(s)

• Francis, George K.
• Edelsbrunner, Herbert

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

graph theory

Language

en

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/29956

Copyright and License Information

Copyright 1997 Christopher M. Hartman

Owning Collections