rao@durga.usc.edu (Anil Rao) (02/02/91)
I am interested in the following graph problem. ----------------------------------------------------------------- Given an undirected graph G over n*n vertices such that the degree of each vertex is bounded by a constant, say d. Is the vertex set of such graphs always partitionable into n sets, V1, V2, ... , Vn of n vertices each, such that the number of edges in E(i,j), for all i,j ranging from 1,...,n, is bounded by a constant (a function of d), where E(i,j) = set of edges with one end in Vi and another in Vj ? ------------------------------------------------------------------ If anyone has ideas on the solution to this problem, or references to this or similar problems, please send me email at rao@durga.usc.edu Thanks, Anil Rao. SAL 337, Dept. of Elec. Engg. - Systems, USC, Los Angeles, CA 90089-0781. USA.
rao@durga.usc.edu (Anil Rao) (02/10/91)
I had previously posted this to sci.math. I apologise to regular readers of both newsgroups for the repetition. I am interested in the following graph problem. ----------------------------------------------------------------- Given an undirected graph G over n*n vertices such that the degree of each vertex is bounded by a constant, say d. Is the vertex set of such graphs always partitionable into n sets, V1, V2, ... , Vn of n vertices each, such that the number of edges in E(i,j), for all i,j ranging from 1,...,n, is bounded by a constant (a function of d), where E(i,j) = set of edges with one end in Vi and another in Vj ? ------------------------------------------------------------------ If anyone has ideas on the solution to this problem, or references to this or similar problems, please send email to rao@durga.usc.edu Thanks, Anil Rao. SAL 337, Dept. of Elec. Engg. - Systems, USC, Los Angeles, CA 90089-0781. USA.