THE NUMBER OF DEPENDENT ARCS IN AN ACYCLIC ORIENTATION

Let G be a graph with n nodes, e edges, chromatic number X, and girth g. In an acyclic orientation of G, an arc is dependent if its reversal creates a cycle. It is well known that if X < g, then G has an acycli c orientation without dependent arcs. Edelman showed that if G is conn ected, then every acyclic orientation has at most e - n + 1 dependent arcs. We show that if G is connected and X < g, then G has an acyclic orientation with exactly d dependent arcs for all d less than or equal to e - n + 1. We also give bounds on the minimum number of dependent arcs in graphs with X greater than or equal to g. (C) 1997 Academic Pr ess.