Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Perfectly orderable graph
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.