Théorie topologique des graphesEn mathématiques, la théorie topologique des graphes est une branche de la théorie des graphes . Elle étudie entre autres les plongements de graphes dans des surfaces, les graphiques en tant qu'espaces topologiques ainsi que les immersions de graphes. Un plongement d'un graphe dans une surface donnée, une sphère par exemple, est une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Un problème fondamental de la théorie topologique des graphes, souvent présenté comme un casse - tête mathématique, est le problème des trois chalets.
Graphe nulEn mathématiques, plus spécialement en théorie des graphes, un graphe nul désigne soit un graphe d'ordre zéro (i.e. sans sommets), soit un graphe avec sommets mais sans arêtes (on parle aussi dans ce dernier cas de graphe vide). Lorsqu'un graphe nul contient des sommets tous isolés, on le note où représente le nombre de sommets du graphe. La taille (i.e. le nombre d'arêtes ou d'arcs) d'un graphe nul est toujours zéro. L'ordre (i.e. le nombre de sommets) d'un graphe nul n'est pas nécessairement zéro.
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.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
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.
Mineur (théorie des graphes)La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .
Circular-arc graphIn graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect. Formally, let be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where and A family of arcs that corresponds to G is called an arc model. demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in time.
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
Graphe de Ramanujanvignette|Le graphe de Pappus, qui selon les valeurs propres de sa matrice de connexion, est aussi un graphe de Ramanujan. Un graphe de Ramanujan, nommé d'après Srinivasa Ramanujan, est un graphe régulier dont le trou spectral (spectral gap) est presque aussi grand que possible. De tels graphes sont d'excellents graphes expanseurs. Autrement dit, il s'agit d'une famille de graphes où chaque sommet a un même degré (régulier) et où les deux valeurs propres les plus élevées ont une différence presque aussi grande que possible.
Théorie des graphes extrémauxEn théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits. L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes.
