$p$ as the set of nodes connected to node $p$, but excluding it; the cardinality of this set, $D_p := |\mathcal{N}_p|$, is the degree of node $p$.

[[**Node coloring.**]{}]{} Given a network $\mathcal{G}$, a (node) coloring scheme is an assignment of numbers, which we call colors, to the nodes of the network such that no adjacent nodes have the same color. The colors will be represented as a set $\mathcal{C} = \{1,2,\ldots,C\}$, where $C$ is the total number of colors. For each color $c$, the set $\mathcal{C}_c \subset \mathcal{V}$ represents the nodes with color $c$, and $C_c$ is the number of nodes with that color, i.e., $|\mathcal{C}_c| = C_c$. A network $\mathcal{G}$ can have several coloring schemes, and $\chi(\mathcal{G})$ denotes the minimum number of colors required to color it; it is called its chromatic number. Finding a coloring scheme that uses only $\chi(\mathcal{G})$ colors is NP-hard for $\chi(\mathcal{G}) > 2$. Node-coloring is very important in wireless networks, since it is used in some medium access (MAC) protocols; consequently, many distributed node-coloring algorithms have been proposed, e.g., [@Kuhn06ComplexityDistributedGraphColoring; @Leith06DistributedLearningAlgorithms; @Duffy09ComplexityAnalysisDecentralizedGraphColoring; @Linial92LocalityDistributedGraphAlgorithms]. Henceforth, we will assume that the network $\mathcal{G}$ is given together with a coloring scheme $\mathcal{C}$.

[[**Problem manipulations.**]{}]{} We start 