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