Concept
Graphe de comparabilité
Concepts associés (21)
Order dimension
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. first studied order dimension; for a more detailed treatment of this subject than provided here, see . The dimension of a poset P is the least integer t for which there exists a family of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions.
Perfect graph theorem
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.
Graphe scindé
vignette|240x240px| Un graphe scindé, partitionné en une clique et un ensemble stable. En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979 .
Graphe à seuil
vignette| Un graphe à seuil. En théorie des graphes, un graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : Ajout d'un sommet isolé au graphe. Ajout d'un sommet dominant au graphe, c'est-à-dire d'un sommet connecté à tous les autres sommets. Par exemple, le graphe de la figure ci-contre est un graphe de seuil : il peut être construit en commençant par un graphe à un seul sommet (sommet 1), puis en ajoutant les sept autres dans l'ordre dans lequel ils sont numérotés, les sommets noirs comme sommets isolés et les sommets rouges comme sommets dominants.
Graphe parfait
En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
Forbidden graph characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.
Graphe trivialement parfait
vignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
Problème de la plus longue chaîne
vignette|Par suppression d'une arête rouge arbitraire, ce cycle hamiltonien donne une chaîne de longueur maximale. En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin.
Coloration gloutonne
droite|vignette|upright=1.4| Deux colorations gloutonnes du même graphe couronne pour des ordres différents sur les sommets. La numérotation de droite se généralise aux graphes bicolores à n sommets, et l'algorithme glouton utilise couleurs. Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible.
Perfectly orderable graph
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.