Coloration de graphethumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.
Coloration des arêtes d'un graphethumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.
Circle graphIn graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other. gives an O(n2)-time algorithm that tests whether a given n-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. A number of other problems that are NP-complete on general graphs have polynomial time algorithms when restricted to circle graphs.
Graphe cordalthumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
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.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Théorème de Grötzschvignette| Une 3-coloration d'un graphe planaire sans triangle En mathématiques, et particulièrement en théorie des graphes, le théorème de Grötzsch est un théorème qui affirme qu'un graphe planaire sans triangle peut être coloré avec seulement trois couleurs. Selon le théorème des quatre couleurs, les sommets de tout graphe planaire peuvent être colorés en utilisant au plus quatre couleurs, de sorte que les deux extrémités de chaque arête aient des couleurs différentes ; par le théorème de Grötzsch, trois couleurs suffisent pour les graphes planaires qui ne contiennent pas trois sommets mutuellement adjacents.
Polynôme chromatiqueEn mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
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 bipartiEn théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.
Graphe planaire extérieurvignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes.
Intersection number (graph theory)In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .
Segment (mathématiques)vignette|Le segment . En géométrie, un segment de droite (souvent abrégé en « segment ») est une portion de droite délimitée par deux points, appelés extrémités du segment. Un segment reliant deux points et est noté ou et représente la partie de la droite qui se situe « entre » les points et . Intuitivement, un segment correspond à un fil tendu entre deux points, en négligeant l’épaisseur du fil et la déformation due à son poids.
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 .
Implicit graphIn the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function. The notion of an implicit graph is common in various search algorithms which are described in terms of graphs. In this context, an implicit graph may be defined as a set of rules to define all neighbors for any specified vertex.
Droite (mathématiques)En géométrie, le mot droite désigne un objet formé de points alignés. Une droite est illimitée des deux côtés, et sans épaisseur (dans la pratique, elle est représentée, sur une feuille, par une ligne droite ayant bien entendu des limites — celles de la feuille — et une épaisseur — celle du crayon). Pour les Anciens, la droite était un concept « allant de soi », si « évident » que l'on négligeait de préciser de quoi l'on parlait. L'un des premiers à formaliser la notion de droite fut le Grec Euclide dans ses Éléments.
Graphe à distance héréditairevignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits.
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 médianEn théorie des graphes, un graphe médian est un type de graphe. Étant donné un triplet de nœuds dans un graphe, les médians de ces sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets. Un graphe médian est un graphe tel que pour tout triplet de nœuds il existe un unique médian. En théorie des graphes, les médians d'un triplet de sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets. Autrement dit, si est l'ensemble de sommets sur les plus courts chemins entre et , alors l'ensemble des sommets médians est .
