Editing Graph coloring (section)

=== Decentralized algorithms ===
Decentralized algorithms are ones where no [[message passing]] is allowed (in contrast to distributed algorithms where local message passing takes places), and efficient decentralized algorithms exist that will color a graph if a proper coloring exists.  These assume that a vertex is able to sense whether any of its neighbors are using the same color as the vertex i.e., whether a local conflict exists.  This is a mild assumption in many applications e.g. in wireless channel allocation it is usually reasonable to assume that a station will be able to detect whether other interfering transmitters are using the same channel (e.g. by measuring the SINR).  This sensing information is sufficient to allow algorithms based on learning automata to find a proper graph coloring with probability one.<ref>E.g. see {{harvtxt|Leith|Clifford|2006}} and {{harvtxt|Duffy|O'Connell|Sapozhnikov|2008}}.</ref>