# Difference between revisions of "Acyclic orientation"

m (link) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||

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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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. |

## Latest revision as of 16:08, 1 April 2020

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=45019