2026-09-18T23:00:59Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/29956 2023-07-10 col_2142_16340 col_2142_5131 com_2142_16339 com_2142_8903 com_2142_5130

West, Douglas B. Weichsel, Paul M. Francis, George K. Edelsbrunner, Herbert Hartman, Christopher M. 2012-03-01T19:31:13Z 2012-03-01T19:31:13Z 1997 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. Submitted by Sarah Shreeves (sshreeve@illinois.edu) on 2012-03-01T19:31:13Z No. of bitstreams: 1 Hartman_Christopher.pdf: 2653633 bytes, checksum: 1588fa0ba80b477739db059a0e5fc587 (MD5) On behalf of Chris Hartman - email sent to IDEALS-gen on January 11, 2012 Made available in DSpace on 2012-03-01T19:31:13Z (GMT). No. of bitstreams: 1 Hartman_Christopher.pdf: 2653633 bytes, checksum: 1588fa0ba80b477739db059a0e5fc587 (MD5) Previous issue date: 1997 http://hdl.handle.net/2142/29956 en Copyright 1997 Christopher M. Hartman graph theory Extremal problems in graph theory Dissertation / Thesis text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.