Namespaces
Variants
Actions

Difference between revisions of "Acyclic orientation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (fixing spaces)
Line 18: Line 18:
 
from  $  u $
 
from  $  u $
 
to  $  v $
 
to  $  v $
if  $  f ( u ) < f ( v ) $(
+
if  $  f ( u ) < f ( v ) $ (cf. [[Graph colouring|Graph colouring]]). Given an acyclic orientation  $  D $
cf. [[Graph colouring|Graph colouring]]). Given an acyclic orientation  $  D $
 
 
of a connected graph  $  G $
 
of a connected graph  $  G $
 
that is not a forest (cf. also [[Graph, connectivity of a|Graph, connectivity of a]]), let  $  r ( D ) $
 
that is not a forest (cf. also [[Graph, connectivity of a|Graph, connectivity of a]]), let  $  r ( D ) $
Line 32: Line 31:
 
where  $  l ( D ) $
 
where  $  l ( D ) $
 
is the maximum length of a path in an orientation  $  D $
 
is the maximum length of a path in an orientation  $  D $
of  $  G $(
+
of  $  G $ (equality holds for the orientation defined above).
equality holds for the orientation defined above).
 
  
 
R.P. Stanley [[#References|[a11]]] proved that the number of acyclic orientations of a graph  $  G $
 
R.P. Stanley [[#References|[a11]]] proved that the number of acyclic orientations of a graph  $  G $
 
is the value at  $  k = - 1 $
 
is the value at  $  k = - 1 $
of the [[chromatic polynomial]]  $  \chi ( G;k ) $(
+
of the [[chromatic polynomial]]  $  \chi ( G;k ) $ (computing this number is  $  \# P $-complete [[#References|[a13]]]). More generally, suppose that  $  D $
computing this number is  $  \# P $-
+
is an acyclic orientation of an  $  n $-vertex graph  $  G $
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 \} } $
 
and that  $  f : {V ( G ) } \rightarrow {\{ 1 \dots k \} } $
is a  $  k $-
+
is a  $  k $-colouring of  $  G $.  
colouring of  $  G $.  
 
 
One says that  $  ( D,f ) $
 
One says that  $  ( D,f ) $
 
is a compatible pair if  $  uv \in E ( D ) $
 
is a compatible pair if  $  uv \in E ( D ) $
Line 55: Line 49:
 
An edge in an acyclic orientation is dependent when reversing it would create a cycle. The acyclic orientation graph  $  { \mathop{\rm AO} } ( G ) $
 
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 $,  
 
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 $-
+
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 $
vertex graph  $  G $
 
 
has at least  $  n - 1 $
 
has at least  $  n - 1 $
 
independent edges (deletion of dependent edges does not disconnect  $  G $),  
 
independent edges (deletion of dependent edges does not disconnect  $  G $),  
Line 67: Line 60:
 
has  $  m $
 
has  $  m $
 
edges,  $  { \mathop{\rm AO} } ( G ) $
 
edges,  $  { \mathop{\rm AO} } ( G ) $
is isomorphic to an [[induced subgraph]] of the  $  m $-
+
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 ) $
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 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.
 
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.
Line 79: Line 71:
 
there exist acyclic orientations in which every edge is independent.
 
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} $-
+
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 ) $)  
complete. The smallest triangle-free graph with chromatic number  $  4 $(
+
is the  $  11 $-vertex Grötzsch graph, and it is not a cover graph.
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 $
 
Other types of acyclic orientations characterize important families of graphs. An acyclic orientation  $  D $
Line 96: Line 85:
 
is the size of the largest clique in  $  H $.  
 
is the size of the largest clique in  $  H $.  
 
V. Chvátal [[#References|[a3]]] proved that  $  G $
 
V. Chvátal [[#References|[a3]]] proved that  $  G $
is perfectly orderable if and only if it has an acyclic orientation having no induced  $  4 $-
+
is perfectly orderable if and only if it has an acyclic orientation having no induced  $  4 $-vertex path with both end-edges oriented outward.
vertex path with both end-edges oriented outward.
 
  
 
Let  $  c ( G ) $
 
Let  $  c ( G ) $

Revision as of 05:49, 13 June 2022


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 -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=52392
This article was adapted from an original article by D. West (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article