Lesson plan

acyclic orientation

, assignments of a direction to each cycle edge that make the resulting directed graph 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.

Back to article

Article summary

, assignments of a direction to each cycle edge that make the resulting directed graph 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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.