Namespaces
Variants
Actions

Difference between revisions of "Acyclic orientation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (→‎References: latexify)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
<!--
 +
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 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102801.png" /> can be obtained from a proper colouring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102802.png" /> by orienting each edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102803.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102804.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102805.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102806.png" /> (cf. [[Graph colouring|Graph colouring]]). Given an acyclic orientation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102807.png" /> of a connected graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102808.png" /> that is not a forest (cf. also [[Graph, connectivity of a|Graph, connectivity of a]]), let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a1102809.png" /> be the maximum over all cycles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028010.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028012.png" /> has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028013.png" /> forward edges and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028014.png" /> backward edges in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028015.png" />. G.J. Minty [[#References|[a7]]] proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028016.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028017.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028018.png" /> is the maximum length of a path in an orientation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028019.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028020.png" /> (equality holds for the orientation defined above).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028021.png" /> is the value at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028022.png" /> of the chromatic polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028023.png" /> (computing this number is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028025.png" />-complete [[#References|[a13]]]). More generally, suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028026.png" /> is an acyclic orientation of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028027.png" />-vertex graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028028.png" /> and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028029.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028030.png" />-colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028031.png" />. One says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028032.png" /> is a compatible pair if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028033.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028034.png" />. Stanley proved that the number of compatible pairs is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028035.png" />. This relationship is an instance of combinatorial reciprocity. Stanley [[#References|[a12]]] further generalized this to count acyclic orientations with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028036.png" /> sinks. C. Greene [[#References|[a6]]] proved that the acyclic orientations of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028037.png" /> 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.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028039.png" /> is the graph whose vertices are the acyclic orientations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028040.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028041.png" />-vertex graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028042.png" /> has at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028043.png" /> independent edges (deletion of dependent edges does not disconnect <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028044.png" />), and this is best possible (equality holds when the independent edges arise from a depth-first search tree). Thus, the minimum degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028045.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028046.png" />. P.H. Edelman (see also [[#References|[a10]]]) proved that the connectivity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028047.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028048.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028049.png" /> has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028050.png" /> edges, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028051.png" /> is isomorphic to an [[induced subgraph]] of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028053.png" />-dimensional hypercube and is thus bipartite (cf. [[Graph, bipartite|Graph, bipartite]]). It is conjectured that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028054.png" /> is Hamiltonian when its two partite sets have the same size. G. Pruesse and F. Ruskey [[#References|[a8]]] proved that the Cartesian product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028055.png" /> 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 $  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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028056.png" /> is less than the girth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028057.png" />, the list of vertex degrees in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028058.png" /> includes all values from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028059.png" /> up to the maximum degree [[#References|[a4]]]. It is unknown whether this is true for all graphs. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028060.png" />, there exist acyclic orientations in which every edge is independent.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028062.png" />-complete. The smallest triangle-free graph with chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028063.png" /> (violating the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028064.png" />) is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028065.png" />-vertex Grötzsch graph, and it is not a cover graph.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028066.png" /> of a simple graph is a transitive orientation if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028067.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028068.png" /> together imply <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028069.png" />. The graphs having transitive orientations are the comparability graphs of partially ordered sets. A graph is perfectly orderable if it has a vertex ordering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028070.png" /> such that greedily colouring the vertices of any induced subgraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028071.png" /> in the order specified by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028072.png" /> uses only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028073.png" /> colours, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028074.png" /> is the size of the largest clique in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028075.png" />. V. Chvátal [[#References|[a3]]] proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028076.png" /> is perfectly orderable if and only if it has an acyclic orientation having no induced <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028077.png" />-vertex path with both end-edges oriented outward.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028078.png" /> be the worst-case number of edges that must be probed by an algorithm that finds an unknown acyclic orientation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028079.png" />. A graph is exhaustive if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028080.png" />. Graphs having an acyclic orientation in which every edge is independent are exhaustive. For bounds on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028081.png" /> in terms of the independence number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028082.png" /> see [[#References|[a1]]]. N. Alon and Zs. Tuza [[#References|[a2]]] proved that for the random graph with constant edge probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028083.png" />, almost surely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110280/a11028084.png" />. Both papers also study exhaustive graphs.
+
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.
 
Acyclic orientations have computational applications in percolation, network reliability, neural networks, parallel sorting, scheduling, etc.
  
 
====References====
 
====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>
+
<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 $n$-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>

Latest revision as of 06:32, 26 March 2023


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