Average distance in colored graphs (Q2746481)

The colored distance of a graph \(G\) is the sum of the distances between all unordered pairs of vertices having different colors. For a fixed supply \(s\) of colors the generalization of the concept of median \(d_s(G)\) is defined as the minimum colored distance over all colorings with \(s\). The authors explore a bound of this parameter, especially a lower bound, and the particular case of balanced 2-colorings. They show that the general problem is NP-hard but there is a polynomial-time algorithm for finding a colored distance of a tree for two colors.