The talk deals with vertex coloring algorithms: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color. Distributed algorithms that find a (Delta+1)-coloring in a logarithmic number of communication rounds, with high probability, are known since more than a decade. But what if the edges have orientations, i.e., the endpoints of an edge agree on its orientation (while bits may still flow in both directions)?
Interestingly, for the cycle in which all edges have the same orientation, we show that a simple randomized algorithm can achieve a 3-coloring with only O(sqrt{log n}) rounds of bit transmissions, with high probability (w.h.p.). This result is tight because we also show that the bit complexity of coloring an oriented cycle is Omega(sqrt{log n}), w.h.p., no matter how many colors are allowed. The 3-coloring algorithm can be easily extended to provide a (Delta+1)-coloring for oriented graphs of maximum degree Delta in O(sqrt{log n}) rounds of bit transmissions, w.h.p., if Delta is a constant, and the graph does not contain an oriented cycle of length less than sqrt{log n}. Using more complex algorithms, we show how to obtain an O(Delta)-coloring for arbitrary oriented graphs with maximum degree Delta and with no oriented cycles of length at most sqrt{log n}, using essentially O(log Delta+ sqrt{log n}) rounds of bit transmissions.