Ê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
Perfect graph theorem
Résumé
In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.
A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph. Perfect graphs include many important graphs classes including bipartite graphs, chordal graphs, and comparability graphs.
The complement of a graph has an edge between two vertices if and only if the original graph does not have an edge between the same two vertices. Thus, a clique in the original graph becomes an independent set in the complement and a coloring of the original graph becomes a clique cover of the complement.
The perfect graph theorem states:
The complement of a perfect graph is perfect.
Equivalently, in a perfect graph, the size of the maximum independent set equals the minimum number of cliques in a clique cover.
Let G be a cycle graph of odd length greater than three (a so-called "odd hole"). Then G requires at least three colors in any coloring, but has no triangle, so it is not perfect. By the perfect graph theorem, the complement of G (an "odd antihole") must therefore also not be perfect. If G is a cycle of five vertices, it is isomorphic to its complement, but this property is not true for longer odd cycles, and it is not as trivial to compute the clique number and chromatic number in an odd antihole as it is in an odd hole. As the strong perfect graph theorem states, the odd holes and odd antiholes turn out to be the minimal forbidden induced subgraphs for the perfect graphs.
In a nontrivial bipartite graph, the optimal number of colors is (by definition) two, and (since bipartite graphs are triangle-free) the maximum clique size is also two.
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.
Publications associées (32)