Extremal problems in graph theory 论文

摘要

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.
\n
\nThe 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.
\n
\nWe 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.
\n
\nThe 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.$
\n
\nThe 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.
\n
\nThe 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.
\n
\nLet ${\\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).
\n
\nThe 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.