Naatz, Michael2022-05-112022-05-1120002197-8085https://depositonce.tu-berlin.de/handle/11303/16892http://dx.doi.org/10.14279/depositonce-15670Given a graph G and an orientation~σ of some of its edges, consider the graph AOσ(G) which is defined as follows: The vertices are the acyclic orientations of G which agree with~σ, and two of these are adjacent if they differ only by the reversal of a single edge. AOσ(G) is easily seen to be bipartite. The purpose of this note is to show that it need not contain a Hamilton path even if both partite sets have the same cardinality. This answers a question of Carla D. Savage (SIAM Rev. 39(4):605-629,1997) and sheds new light onto two well-known open questions in the field of combinatorial Gray codes.en510 MathematikHamilton pathacyclic orientationposetlinear extensionadjacent transpositionResearch Paper