Graphe de permutationEn théorie des graphes, un graphe de permutation est un graphe non orienté dont les sommets représentent les éléments d'une permutation, et dont les arêtes relient les paires de sommets qui sont inversés dans la permutation. On peut aussi définir les graphes de permutations de manière géométrique : ce sont les graphes d'intersections de segments dont les extrémités sont sur deux droites parallèles. On définit les graphes de permutation de la manière suivante.
Graphe de blocsvignette|upright=1.4|Un graphe de blocs. En théorie des graphes, une branche des mathématiques combinatoires, un graphe de blocs ou arbre de cliques est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique. Les graphes de blocs ont été appelés aussi arbres Husimi (d'après Kôdi Husimi), mais ce nom fait plus référence aux graphes cactus, qui sont des graphes dans lesquels chaque composante biconnexe non triviale est un cycle.
Stable (théorie des graphes)thumb|280px|L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G).
Claw-free graphIn graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph.
Graphe d'intervallesEn théorie des graphes, un graphe d'intervalles est le graphe d'intersection d'un ensemble d'intervalles de la droite réelle. Chaque sommet du graphe d'intervalles représente un intervalle de l'ensemble, et une arête relie deux sommets lorsque les deux intervalles correspondants s'intersectent. Etant donnés des intervalles , le graphe d'intervalle correspondant est où et Les graphes d'intervalles sont utilisés pour modéliser les problèmes d'allocation de ressources en recherche opérationnelle et en théorie de la planification.
BoxicityIn graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices. The figure shows a graph with six vertices, and a representation of this graph as an intersection graph of rectangles (two-dimensional boxes).
String graphIn graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G. described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs.
Trapezoid graphIn graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988.
Graphe d'intervalles propreUn graphe d'intervalles propre est un graphe d'intervalles possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre. Un graphe d'intervalles propre est nécessairement un graphe sans griffe. Soit un graphe possédant une griffe comme sous-graphe induit. On appelle les quatre sommets de la griffe d'intervalles respectives ,, et tels que le sommet soit celui relié aux trois autres et que . Comme la griffe est un graphe induit, , et ne sont pas voisins dans . On a donc .
Geometric graph theoryGeometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013).
