Acyclic orientation

Quality 0.50 · 5 views · Updated 2 months ago

Element of graph theory

title: "Acyclic orientation" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-theory-objects"] description: "Element of graph theory" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Acyclic_orientation" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Element of graph theory ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/0/09/Acyclic_orientations_of_C4.svg" caption="acyclic]]. Two orientations are shown as adjacent when they differ in the direction of a single edge."] ::

In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation.

The chromatic number of any graph equals one more than the length of the longest path in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings. The planar dual of an acyclic orientation is a totally cyclic orientation, and vice versa. The family of all acyclic orientations can be given the structure of a partial cube by making two orientations adjacent when they differ in the direction of a single edge.

Orientations of trees are always acyclic, and give rise to polytrees. Acyclic orientations of complete graphs are called transitive tournaments. The bipolar orientations are a special case of the acyclic orientations in which there is exactly one source and one sink; every transitive tournament is bipolar.

Construction

Every graph has an acyclic orientation. One way to generate an acyclic orientation is to place the vertices into a sequence, and then direct each edge from the earlier of its endpoints in the sequence to the later endpoint. The vertex sequence then becomes a topological ordering of the resulting directed acyclic graph (DAG), and every topological ordering of this DAG generates the same orientation.

Because every DAG has a topological ordering, every acyclic orientation can be constructed in this way. However, it is possible for different vertex sequences to give rise to the same acyclic orientation, when the resulting DAG has multiple topological orderings. For instance, for a four-vertex cycle graph (shown), there are 24 different vertex sequences, but only 14 possible acyclic orientations.

Relation to coloring

The Gallai–Hasse–Roy–Vitaver theorem states that a graph has an acyclic orientation in which the longest path has at most k vertices if and only if it can be colored with at most k colors.{{citation | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | contribution = Theorem 3.13 | doi = 10.1007/978-3-642-27875-4 | isbn = 978-3-642-27874-7 | location = Heidelberg | mr = 2920058 | page = 42 | publisher = Springer | series = Algorithms and Combinatorics | title = Sparsity: Graphs, Structures, and Algorithms | volume = 28 | year = 2012 | doi-broken-date = 30 January 2026 }}.

The number of acyclic orientations may be counted using the chromatic polynomial \chi_G, whose value at a positive integer k is the number of k-colorings of the graph. Every graph G has exactly |\chi_G(-1)| different acyclic orientations, so in this sense an acyclic orientation can be interpreted as a coloring with −1 colors.

Duality

For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: if G is a planar graph, and orientations of G are transferred to orientations of the planar dual graph of G by turning each edge 90 degrees clockwise, then a totally cyclic orientation of G corresponds in this way to an acyclic orientation of the dual graph and vice versa.{{citation | last = Welsh | first = Dominic | contribution = Approximate counting | doi = 10.1017/CBO9780511662119.010 | location = Cambridge | mr = 1477750 | pages = 287–323 | publisher = Cambridge Univ. Press | series = London Math. Soc. Lecture Note Ser. | title = Surveys in combinatorics, 1997 (London) | volume = 241 | year = 1997| isbn = 978-0-521-59840-8

Like the chromatic polynomial, the Tutte polynomial T_G of a graph G, can be used to count the number of acyclic orientations of G as T_G(2,0). The duality between acyclic and totally cyclic orientations of planar graphs extends in this form to nonplanar graphs as well: the Tutte polynomial of the dual graph of a planar graph is obtained by swapping the arguments of T_G, and the number of totally cyclic orientations of a graph G is T_G(0,2), also obtained by swapping the arguments of the formula for the number of acyclic orientations.{{citation | last = Las Vergnas | first = Michel | authorlink = Michel Las Vergnas | doi = 10.1016/0095-8956(80)90082-9 | issue = 2 | journal = Journal of Combinatorial Theory | series = Series B | mr = 586435 | pages = 231–243 | title = Convexity in oriented matroids | volume = 29 | year = 1980| doi-access =

Edge flipping

The set of all acyclic orientations of a given graph may be given the structure of a partial cube, in which two acyclic orientations are adjacent whenever they differ in the direction of a single edge.{{citation |last1 = Fukuda |first1 = Komei | author1-link = Komei Fukuda |last2 = Prodon |first2 = Alain |last3 = Sakuma |first3 = Tadashi |doi = 10.1016/S0304-3975(00)00226-7 |issue = 1–2 |journal = Theoretical Computer Science |mr = 1846912 |pages = 9–16 |title = Notes on acyclic orientations and the shelling lemma |volume = 263 |year = 2001 |doi-access= free

Special cases

::figure[src="https://upload.wikimedia.org/wikipedia/commons/6/61/Polytree.svg" caption="A polytree, the result of acyclically orienting a tree"] ::

Every orientation of a tree is acyclic. The directed acyclic graph resulting from such an orientation is called a polytree. {{citation | last1 = Dasgupta| first1 = Sanjoy | contribution = Learning polytrees | pages = 134–141 | title = Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999 | url = http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf | year = 1999}}.

An acyclic orientation of a complete graph is called a transitive tournament, and is equivalent to a total ordering of the graph's vertices. In such an orientation there is in particular exactly one source and exactly one sink.

More generally, an acyclic orientation of an arbitrary graph that has a unique source and a unique sink is called a bipolar orientation.{{citation | last1 = de Fraysseix | first1 = Hubert | last2 = de Mendez | first2 = Patrice Ossona | last3 = Rosenstiehl | first3 = Pierre | author3-link = Rosenstiehl | doi = 10.1016/0166-218X(94)00085-R | issue = 2–3 | journal = Discrete Applied Mathematics | mr = 1318743 | pages = 157–179 | title = Bipolar orientations revisited | volume = 56 | year = 1995| doi-access = free

A transitive orientation of a graph is an acyclic orientation that equals its own transitive closure. Not every graph has a transitive orientation; the graphs that do are the comparability graphs.{{citation | last = Ghouila-Houri | first = Alain | title = Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre | journal = Les Comptes rendus de l'Académie des sciences | volume = 254 | year = 1962 | pages = 1370–1371 | mr =0172275}}. Complete graphs are special cases of comparability graphs, and transitive tournaments are special cases of transitive orientations.

References

Stanley, Richard P.. (1973). "Acyclic orientations of graphs". Discrete Mathematics.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::