# Acyclic orientation

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An orientation (assignment of direction) of each edge of a graph such that no cycle in the graph is a cycle (consistently oriented) in the resulting directed graph (cf. Graph, oriented).

An acyclic orientation of a graph $G$ can be obtained from a proper colouring $f$ by orienting each edge $uv$ from $u$ to $v$ if $f ( u ) < f ( v )$( cf. Graph colouring). Given an acyclic orientation $D$ of a connected graph $G$ that is not a forest (cf. also Graph, connectivity of a), let $r ( D )$ be the maximum over all cycles in $G$ of $\lceil {a / b } \rceil$, where $C$ has $a$ forward edges and $b$ backward edges in $D$. G.J. Minty [a7] proved that $\chi ( G ) \leq 1 + r ( D )$ and that this is best possible (equality holds for the acyclic orientation obtained above from an optimal colouring). Minty's theorem implies the related Gallai–Roy theorem ([a5], [a9], [a14]) that $l ( D ) \geq \chi ( G ) - 1$ where $l ( D )$ is the maximum length of a path in an orientation $D$ of $G$( equality holds for the orientation defined above).

R.P. Stanley [a11] proved that the number of acyclic orientations of a graph $G$ is the value at $k = - 1$ of the chromatic polynomial $\chi ( G;k )$( computing this number is $\# P$- complete [a13]). More generally, suppose that $D$ is an acyclic orientation of an $n$- vertex graph $G$ and that $f : {V ( G ) } \rightarrow {\{ 1 \dots k \} }$ is a $k$- colouring of $G$. One says that $( D,f )$ is a compatible pair if $uv \in E ( D )$ implies $f ( u ) \leq f ( v )$. Stanley proved that the number of compatible pairs is $( - 1 ) ^ {n} \chi ( G; - k )$. This relationship is an instance of combinatorial reciprocity. Stanley [a12] further generalized this to count acyclic orientations with $j$ sinks. C. Greene [a6] proved that the acyclic orientations of a graph $G$ are in one-to-one correspondence with the regions of an associated arrangement of hyperplanes; T. Zaslavsky [a15] has generalized this to acyclic orientations of signed graphs.

An edge in an acyclic orientation is dependent when reversing it would create a cycle. The acyclic orientation graph ${ \mathop{\rm AO} } ( G )$ is the graph whose vertices are the acyclic orientations of $G$, with two vertices adjacent when they differ by the reversal of an edge; the degree of a vertex is its number of independent edges. Every acyclic orientation of a connected $n$- vertex graph $G$ has at least $n - 1$ independent edges (deletion of dependent edges does not disconnect $G$), and this is best possible (equality holds when the independent edges arise from a depth-first search tree). Thus, the minimum degree of ${ \mathop{\rm AO} } ( G )$ is $n - 1$. P.H. Edelman (see also [a10]) proved that the connectivity of ${ \mathop{\rm AO} } ( G )$ is $n - 1$.

When $G$ has $m$ edges, ${ \mathop{\rm AO} } ( G )$ is isomorphic to an induced subgraph of the $m$- dimensional hypercube and is thus bipartite (cf. Graph, bipartite). It is conjectured that ${ \mathop{\rm AO} } ( G )$ is Hamiltonian when its two partite sets have the same size. G. Pruesse and F. Ruskey [a8] proved that the Cartesian product ${ \mathop{\rm AO} } ( G ) \times K _ {2}$ is always Hamiltonian. These Hamiltonicity questions relate to the combinatorial Gray code problem (cf. Gray code) of listing the acyclic orientations by reversing one edge at a time.

When $\chi ( G )$ is less than the girth of $G$, the list of vertex degrees in ${ \mathop{\rm AO} } ( G )$ includes all values from $n - 1$ up to the maximum degree [a4]. It is unknown whether this is true for all graphs. When $\chi ( G ) < { \mathop{\rm girth} } ( G )$, there exist acyclic orientations in which every edge is independent.

A graph has an acyclic orientation in which every edge is independent if and only if it is a cover graph; this acyclic orientation is the cover relation of a partially ordered set (cf. Partial order). Recognition of cover graphs is ${\mathcal N} {\mathcal P}$- complete. The smallest triangle-free graph with chromatic number $4$( violating the condition $\chi ( G ) < { \mathop{\rm girth} } ( G )$) is the $11$- vertex Grötzsch graph, and it is not a cover graph.

Other types of acyclic orientations characterize important families of graphs. An acyclic orientation $D$ of a simple graph is a transitive orientation if $xy \in E ( D )$ and $yz \in E ( D )$ together imply $xz \in E ( D )$. The graphs having transitive orientations are the comparability graphs of partially ordered sets. A graph is perfectly orderable if it has a vertex ordering $L$ such that greedily colouring the vertices of any induced subgraph $H$ in the order specified by $L$ uses only $\omega ( H )$ colours, where $\omega ( H )$ is the size of the largest clique in $H$. V. Chvátal [a3] proved that $G$ is perfectly orderable if and only if it has an acyclic orientation having no induced $4$- vertex path with both end-edges oriented outward.

Let $c ( G )$ be the worst-case number of edges that must be probed by an algorithm that finds an unknown acyclic orientation of $G$. A graph is exhaustive if $c ( G ) = | {E ( G ) } |$. Graphs having an acyclic orientation in which every edge is independent are exhaustive. For bounds on $c ( G )$ in terms of the independence number of $G$ see [a1]. N. Alon and Zs. Tuza [a2] proved that for the random graph with constant edge probability $p$, almost surely $c ( G ) = \Theta ( n { \mathop{\rm log} } n )$. Both papers also study exhaustive graphs.

Acyclic orientations have computational applications in percolation, network reliability, neural networks, parallel sorting, scheduling, etc.

How to Cite This Entry:
Acyclic orientation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Acyclic_orientation&oldid=45019
This article was adapted from an original article by D. West (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article