Abstract   We want to find an unknown acyclic orientation   O   ∗  of an (undirected) graph  G  by testing for certain edges how they are oriented according to   O   ∗ . How many tests do we need in the worst case? We give upper and lower bounds for this number  c ( G ) in terms of the independence number of  G  and study the class of exhaustive graphs, i.e. graphs satisfying  c ( G ) = | E ( G )|. It is shown that there exist nonexhaustive graphs with arbitrarily large girth. The extremal exhaustive graphs are determined for  n  ⩾ 7.
['Martin Aigner', 'Eberhard Triesch', 'Zsolt Tuza']
Searching for acyclic orientations of graphs