On Equal Chromatic Partition of Interconnection Networks

Abstract

We introduce the concept of equal chromatic partition of networks. This concept is useful for deriving lower bounds and upper bounds for performance ratios of dynamic tree embedding schemes that arise in a wide range of tree-structured parallel computations. We provide necessary and sufficient conditions for the existence of equal chromatic partitions of several classes of interconnection networks which include $X$-Nets, folded hypercubes, $X$-trees, $n$-dimensional tori and $k$y $n$-cubes. We use the pyramid network as an example to show that some networks do not have equal chromatic partitions, but may have near-equal chromatic partitions.