  We consider a decentralized graph coloring model where each vertex only knows
its own color and whether some neighbor has the same color as it. The
networking community has studied this model extensively due to its applications
to channel selection, rate adaptation, etc. Here, we analyze variants of a
simple algorithm of Bhartia et al. [Proc., ACM MOBIHOC, 2016]. In particular,
we introduce a variant which requires only $O(n\log\Delta)$ expected
recolorings that generalizes the coupon collector problem. Finally, we show
that the $O(n\Delta)$ bound Bhartia et al. achieve for their algorithm still
holds and is tight in adversarial scenarios.
