Full Orientability of the Square of a Cycle

Fengwei Xu, Weifan Wang, Ko-Wei Lih

Let D be an acyclic orientation of a simple graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. De…