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 can be obtained from a proper colouring
by orienting each edge
from
to
if
(cf. Graph colouring). Given an acyclic orientation
of a connected graph
that is not a forest (cf. also Graph, connectivity of a), let
be the maximum over all cycles in
of
, where
has
forward edges and
backward edges in
. G.J. Minty [a7] proved that
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
where
is the maximum length of a path in an orientation
of
(equality holds for the orientation defined above).
R.P. Stanley [a11] proved that the number of acyclic orientations of a graph is the value at
of the chromatic polynomial
(computing this number is
-complete [a13]). More generally, suppose that
is an acyclic orientation of an
-vertex graph
and that
is a
-colouring of
. One says that
is a compatible pair if
implies
. Stanley proved that the number of compatible pairs is
. This relationship is an instance of combinatorial reciprocity. Stanley [a12] further generalized this to count acyclic orientations with
sinks. C. Greene [a6] proved that the acyclic orientations of a graph
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 is the graph whose vertices are the acyclic orientations of
, 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
-vertex graph
has at least
independent edges (deletion of dependent edges does not disconnect
), and this is best possible (equality holds when the independent edges arise from a depth-first search tree). Thus, the minimum degree of
is
. P.H. Edelman (see also [a10]) proved that the connectivity of
is
.
When has
edges,
is isomorphic to an induced subgraph of the
-dimensional hypercube and is thus bipartite (cf. Graph, bipartite). It is conjectured that
is Hamiltonian when its two partite sets have the same size. G. Pruesse and F. Ruskey [a8] proved that the Cartesian product
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 is less than the girth of
, the list of vertex degrees in
includes all values from
up to the maximum degree [a4]. It is unknown whether this is true for all graphs. When
, 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 -complete. The smallest triangle-free graph with chromatic number
(violating the condition
) is the
-vertex Grötzsch graph, and it is not a cover graph.
Other types of acyclic orientations characterize important families of graphs. An acyclic orientation of a simple graph is a transitive orientation if
and
together imply
. The graphs having transitive orientations are the comparability graphs of partially ordered sets. A graph is perfectly orderable if it has a vertex ordering
such that greedily colouring the vertices of any induced subgraph
in the order specified by
uses only
colours, where
is the size of the largest clique in
. V. Chvátal [a3] proved that
is perfectly orderable if and only if it has an acyclic orientation having no induced
-vertex path with both end-edges oriented outward.
Let be the worst-case number of edges that must be probed by an algorithm that finds an unknown acyclic orientation of
. A graph is exhaustive if
. Graphs having an acyclic orientation in which every edge is independent are exhaustive. For bounds on
in terms of the independence number of
see [a1]. N. Alon and Zs. Tuza [a2] proved that for the random graph with constant edge probability
, almost surely
. 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 ![]() |
[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 |
Acyclic orientation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Acyclic_orientation&oldid=11691