Acyclic orientation

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.

References

[a1]	M. Aigner, E. Triesch, Zs. Tuza, "Searching for acyclic orientations of graphs" Discrete Math. , 144 (1995) pp. 3–10 (Combinatorics of Ordered Sets (Oberwolfach, 1991))
[a2]	N. Alon, Zs. Tuza, "The acyclic orientation game on random graphs" Random Structures Algorithms , 6 (1995) pp. 261–268 (Proc. Sixth Internat. Sem. Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, (Random Graphs '93; Poznań, 1993))
[a3]	V. Chvátal, "Perfectly ordered graphs" , Topics on perfect graphs , North-Holland math. stud. , 88 , North-Holland (1984) pp. 63–65
[a4]	D.C. Fisher, K. Fraughnaugh, L. Langley, D.B. West, "The number of dependent edges in an acyclic orientation" J. Combin. Th. Appl. (to appear)
[a5]	T. Gallai, "On directed paths and circuits" P. Erdős (ed.) G. Katona (ed.) , Theory of Graphs (Proc. Tihany 1966) , Acad. Press (1968) pp. 115–118
[a6]	C. Greene, "Acyclic orientations" M. Aigner (ed.) , Higher combinatorics , Proc. NATO Adv. Study Inst. (1976) , Reidel (1977) pp. 65–68
[a7]	G.J. Minty, "A theorem on $n$-coloring the points of a linear graph" Amer. Math. Monthly , 69 (1962) pp. 623–624
[a8]	G. Pruesse, F. Ruskey, "The prism of the acyclic orientation graph is Hamiltonian" Electron. J. Combin. , 2 (1995) (Research Paper 5, approx. 6 pp. (electronic))
[a9]	B. Roy, "Nombre chromatique et plus longs chemins d'un graphe" Rev. Française Automat. Informat. Recherche Opérationelle Ser. Rouge , 1 (1967) pp. 127–132
[a10]	C.D. Savage, C.-Q. Zhang, "A note on the connectivity of acyclic orientation graphs" Discrete Math. (to appear)
[a11]	R.P. Stanley, "Acyclic orientations of graphs" Discrete Math. , 5 (1973) pp. 171–178
[a12]	R.P. Stanley, "A symmetric function generalization of the chromatic polynomial of a graph" Adv. Math. , 111 (1995) pp. 166–194
[a13]	D.L. Vertigan, D.J.A. Welsh, "The computational complexity of the Tutte plane: the bipartite case" Combin. Probab. Comput. , 1 (1992) pp. 181–187
[a14]	L.M. Vitaver, "Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix" Dokl. Akad. Nauk. SSSR , 147 (1962) pp. 758–759 (In Russian)
[a15]	T. Zaslavsky, "Orientation of signed graphs" European J. Combin. , 12 (1991) pp. 361–375