Xref: utzoo sci.math:14929 comp.theory:1493
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!durga.usc.edu!rao
From: rao@durga.usc.edu (Anil Rao)
Newsgroups: sci.math,comp.theory
Subject: A Graph partitioning Problem.
Message-ID: <29790@usc>
Date: 2 Feb 91 09:47:28 GMT
Sender: news@usc
Followup-To: sci.math
Organization: University of Southern California, Los Angeles, CA
Lines: 18
Nntp-Posting-Host: durga.usc.edu
Originator: rao@durga.usc.edu

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.