To enable the successful deployment of multi-robot systems (MRS), effective coordination mechanisms must be designed in a principled manner. There is currently little formal work addressing how to design such coordination mechanisms nor is there a formal understanding of the capabilities and performance characteristics that can be expected of various coordination mechanisms in a given task domain. We address this problem by presenting a formal framework from which to discuss and reason about coordination in a MRS and use this formalism to develop a method by which to automatically construct individual robot controllers in a MRS for a given task where the robots have the capability for inter-robot communication but maintain no non-transient state. We present a graph coloring approach to determine the minimal number of unique communication messages necessary such that the task is correctly executed. Understanding the capabilities and limitations of a MRS composed of such robots contributes to the understanding of when and why inter-robot communication is necessary to achieve the desired coordination and when it is not sufficient. We validate our automatic controller construction method in a simulated multi-robot construction domain.