Average distance in colored graphs

For a graph G where the vertices are colored, the colored distance of G is defined as the sum of the distances between all unordered pairs of vertices having different colors. Then for a fixed supply s of colors, d(s)(G) is d efined as the minimum colored distance over all colorings with s. This gene ralizes the concepts of median and average distance. In this paper we explo re bounds on this parameter, especially a natural lower bound and the parti cular case of balanced 2-colorings (equal numbers of red and blue). We show that the genera I problem is NP-ha rd but there is a polynomial-time algor ithm for trees. (C) 2001 John Wiley & Sons, Inc.