On fully orientability of 2-degenerate graphs
Suppose that D is an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define d(min)(G) (d(max)(G)) to be the minimum (maximum) number of d(D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying d(min)(G) <= k <= d(max)(G). We prove that every 2-degenerate graph is fully orientable and give interpretations to their d(min). (c) 2007 Elsevier B.V. All rights reserved.
2-degenerate graph acyclic orientation dependent arc cover graph triangle-free graph graph algorithms