Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!durga.usc.edu!rao
From: rao@durga.usc.edu (Anil Rao)
Newsgroups: comp.theory
Subject: A graph partitioning problem.
Message-ID: <29924@usc>
Date: 9 Feb 91 21:48:01 GMT
Sender: news@usc
Organization: University of Southern California, Los Angeles, CA
Lines: 22
Nntp-Posting-Host: durga.usc.edu
Originator: rao@durga.usc.edu

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.