View source for Acyclic orientation

<!--
a1102801.png
$#A+1 = 80 n = 1
$#C+1 = 80 : ~/encyclopedia/old_files/data/A110/A.1100280 Acyclic orientation
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

An orientation (assignment of direction) of each edge of a [[Graph|graph]] such that no cycle in the graph is a cycle (consistently oriented) in the resulting directed graph (cf. [[Graph, oriented|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|Graph colouring]]). Given an acyclic orientation  $  D $
of a connected graph  $  G $
that is not a forest (cf. also [[Graph, connectivity of a|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 [[#References|[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 ([[#References|[a5]]], [[#References|[a9]]], [[#References|[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 [[#References|[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 [[#References|[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 [[#References|[a12]]] further generalized this to count acyclic orientations with  $  j $
sinks. C. Greene [[#References|[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 [[#References|[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 [[#References|[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|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 [[#References|[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|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 [[#References|[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|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 [[#References|[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 [[#References|[a1]]]. N. Alon and Zs. Tuza [[#References|[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====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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))</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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))</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  V. Chvátal,   "Perfectly ordered graphs" , ''Topics on perfect graphs'' , ''North-Holland math. stud.'' , '''88''' , North-Holland  (1984)  pp. 63–65</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  C. Greene,   "Acyclic orientations"  M. Aigner (ed.) , ''Higher combinatorics'' , ''Proc. NATO Adv. Study Inst. (1976)'' , Reidel  (1977)  pp. 65–68</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  G.J. Minty,   "A theorem on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028085.png" />-coloring the points of a linear graph"  ''Amer. Math. Monthly'' , '''69'''  (1962)  pp. 623–624</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  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))</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  C.D. Savage,   C.-Q. Zhang,   "A note on the connectivity of acyclic orientation graphs"  ''Discrete Math.''  (to appear)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  R.P. Stanley,   "Acyclic orientations of graphs"  ''Discrete Math.'' , '''5'''  (1973)  pp. 171–178</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  R.P. Stanley,   "A symmetric function generalization of the chromatic polynomial of a graph"  ''Adv. Math.'' , '''111'''  (1995)  pp. 166–194</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  T. Zaslavsky,   "Orientation of signed graphs"  ''European J. Combin.'' , '''12'''  (1991)  pp. 361–375</TD></TR></table>