Extremal problems in graph theory
Christopher M. Hartman · 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.