Assertion: graph | /r/HasAspect | acyclic orientation
Facets:
Source sentences:
text: 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.
text: 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.
text: A graph has a k-coloring if and only if it has an acyclic orientation for which the longest path has length at most k; this is the Gallai–Hasse–Roy–Vitaver theorem (Nešetřil & Ossona de Mendez 2012).