Acyclic orientation

From formulasearchengine
Jump to navigation Jump to search

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; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint.

The Gallai–Hasse–Roy–Vitaver theorem states that a graph has an acyclic orientation in which the longest path has k vertices if and only if it can be colored with k colors.[1]

For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: if is a planar graph, and orientations of are transferred to orientations of the planar dual graph of by turning each edge 90 degrees clockwise, then a totally cyclic orientation of corresponds in this way to an acyclic orientation of the dual graph and vice versa.[2] This duality extends to nonplanar graphs as well, via the Tutte polynomial of a graph , which can be used to count both types of orientations: the number of acyclic orientations of is and the number of totally cyclic orientations is .[3] The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial : there are different acyclic orientations.[4] 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.[5]

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 with a unique source and a unique sink is called a bipolar orientation.[6]

References

  1. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  2. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  3. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  4. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  5. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  6. {{#invoke:citation/CS1|citation |CitationClass=citation }}.