Searching for acyclic orientations of graphs (Q1898338)

For an undirected graph \(G\), \(c(G)\) is defined to be the minimum integer \(k\) with the property that there exists a subgraph \(H\) of \(G\) with \(k\) edges such that, no matter how \(H\) is acyclically oriented, this orientation can be extended uniquely to an acyclic orientation of all edges of \(G\). The number of acyclic orientations of \(G\) is denoted by \(a (G)\); the maximum number of independent vertices is denoted by \(\alpha (G)\). A graph \(G \) is exhaustive if \(c(G) = |E (G) |\). Theorem 2. For all graphs \(G\) on \(n\) vertices, \[ n \log_2 {n \over \alpha (G)} - n \log_2e+ {1 \over 2} (2 + \log_2n) < c(G) < \alpha (G) n \left (\log_2 {n \over \alpha (G)} + 1 \right). \] This permits an answer to an orally communicated question of P. Erdös: Corollary 3. If \((\begin{smallmatrix} n \\ 2 \end{smallmatrix}) - |E(G) |= o(n^2)\), then \(c(G) = o(n^2)\) as \(n \to \infty\). For every \(0 < \varepsilon < {1 \over 2}\) there is a \(\delta > 0\) such that, for large \(n\), there exists a graph \(G\) on \(n\) vertices with at least \(({1 \over 2} - \varepsilon) n^2\) edges, satisfying \(c(G) \geq \delta n^2\). A theorem of \textit{J. Nešetřil} and \textit{V. Rödl} [On a probabilistic graph-theoretical method, Proc. Am. Math. Soc. 72, 417-421 (1978; Zbl 0399.05007)] is generalized: Theorem 8. For each natural number \(s\), there exists a nonexhaustive graph with girth at least \(s\). The authors acknowledge that N. Alon and Zs. Tuza have proved that the line graphs of cubic triangle-free graphs need not be exhaustive. The size of an exhaustive graph is bounded: Theorem 10. (i) For all \(n \geq 6\), the number of edges in an exhaustive graph on \(n\) vertices is at most \(\lfloor {n^2 \over 4} \rfloor\). (ii) For all \(n \geq 7\), the complete bipartite graph \(K_{\lfloor {n \over 2}\rfloor, \lfloor {n \over 2} \rfloor}\) is the only exhaustive graph with \(\lfloor {n^2 \over 4} \rfloor\) edges. The paper concludes with two open problems: What is the complexity status of deciding whether \(c(G) \leq k\) for a given graph \(G\) and natural number \(k\)? Is it true that \(c(G) \leq {n^2 \over 4} + o(n^2)\) as \(n \to \infty\)?