Locally computing edge orientations

Slobodan Mitrović, Ronitt Rubinfeld, Mihir Singhal

We consider the question of orienting the edges in a graph $G$ such that every vertex has bounded out-degree. For graphs of arboricity $\hat{I}\pm$, there is an orientation in which every…