Chordal Graphs are Fully Orientable

Abstract

Suppose that $D$ is an acyclic orientation of a graph $G$. An arc of $D$ is called dependent if its reversal creates a directed cycle. Let $d_{min}(G)$ ($d_{max}(G)$) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of $G$. We call $G$ fully orientable if $G$ has an acyclic orientation with exactly $d$ dependent arcs for every $d$ satisfying $d_{min}(G)\le d\le d_{max}(G)$. A graph $G$ is called chordal if every cycle in $G$ of length at least four has a chord. We show that all chordal graphs are fully orientable.