The number of dependent arcs in an acyclic orientation (Q1386477)

Let \(G\) be a graph with \(n\) nodes, \(e\) edges, chromatic number \(\chi\), 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 \(\chi< g\), then \(G\) has an acylic orientation without dependent arcs. Edelman showed that if \(G\) is connected, then every acyclic orientation has at most \(e- n+1\) dependent arcs. We show that if \(G\) is connected and \(\chi< g\), then \(G\) has an acyclic orientation with exactly \(d\) dependent arcs for all \(d\leq e-n+ 1\). We also give bounds on the minimum number of dependent arcs in graphs with \(\chi\geq g\).