Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Perfectly orderable graph
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a <a href="/facts/Greedy_coloring/mKpxpQuG">greedy coloring</a> algorithm with that ordering optimally colors every <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> of the given graph. Perfectly orderable graphs form a special case of the <a href="/facts/Perfect_graph/wcPdhjG9">perfect graphs</a>, and they include the <a href="/facts/Chordal_graph/7hNerUdA">chordal graphs</a>, <a href="/facts/Comparability_graph/dLht35EJ">comparability graphs</a>, and <a href="/facts/Distance-hereditary_graph/T17SFUmL">distance-hereditary graphs</a>. However, testing whether a graph is perfectly orderable is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. </p>