On the optimality of Colour-and-Forward relaying for a class of zero-error primitive relay channels

Recently a new “Colour-and-Forward” relaying strategy was proposed for the zero-error primitive relay channel, a relay channel in which the relay to destination link is out of band and of fixed, error-free capacity. This “Colour-and-Forward” scheme forwards the colour (from a minimum colouring) of the node corresponding to its received signal. This colouring is of a carefully designed graph based on the joint distribution of the relay and destination outputs given the transmit signal. This scheme was used to provide a non-trivial upper bound on the minimum required conference link capacity to allow the overall network to achieve the single-input multi-output (SIMO) upper bound. In this paper, we strengthen the result and show that this upper bound is tight if one wants to achieve the SIMO bound in the overall network for any fixed number of channel uses.