Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Perfectly orderable graph
Summary
In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.
The greedy coloring algorithm, when applied to a given ordering of the vertices of a graph G, considers the vertices of the graph in sequence and assigns each vertex its first available color, the minimum excluded value for the set of colors used by its neighbors. Different vertex orderings may lead this algorithm to use different numbers of colors. There is always an ordering that leads to an optimal coloring – this is true, for instance, of the ordering determined from an optimal coloring by sorting the vertices by their color – but it may be difficult to find.
The perfectly orderable graphs are defined to be the graphs for which there is an ordering that is optimal for the greedy algorithm not just for the graph itself, but for all of its induced subgraphs.
More formally, a graph G is said to be perfectly orderable if there exists an ordering π of the vertices of G, such that every induced subgraph of G is optimally colored by the greedy algorithm using the subsequence of π induced by the vertices of the subgraph. An ordering π has this property exactly when there do not exist four vertices a, b, c, and d for which abcd is an induced path, a appears before b in the ordering, and c appears after d in the ordering.
Perfectly orderable graphs are NP-complete to recognize. However, it is easy to test whether a particular ordering is a perfect ordering of a graph. Consequently, it is also NP-hard to find a perfect ordering of a graph, even if the graph is already known to be perfectly orderable.
Every perfectly orderable graph is a perfect graph.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.