Acyclic orientation
id:
acyclic-orientation-238-3171677
title:
Acyclic orientation
text:
In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge 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
brand slug:
wiki
category slug:
encyclopedia
description:
Element of graph theory
original url:
https://en.wikipedia.org/wiki/Acyclic_orientation
date created:
date modified:
2024-01-23T00:41:58Z
main entity:
{"identifier":"Q4677986","url":"https://www.wikidata.org/entity/Q4677986"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/0/09/Acyclic_orientations_of_C4.svg","width":558,"height":702}
fields total:
13
integrity:
15