En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
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.
thumb|Pour chaque sommet, la liste d'adjacence est représentée en jaune. En algorithmique, une liste d'adjacence est une structure de données utilisée pour représenter un graphe. Cette représentation est particulièrement adaptée aux graphes creux (c'est-à-dire peu denses), contrairement à la matrice d'adjacence adaptée aux graphes denses. La liste d'adjacence d'un graphe non orienté, est la liste des voisins de chaque sommet. Celle d'un graphe orienté est typiquement, pour chaque sommet, la liste de nœuds à la tête de chaque arête ayant le sommet comme queue.
vignette|301x301px| Une instance de coloration de liste du graphe biparti complet K 3,27 avec trois couleurs par sommet. Pour tout choix de couleurs des trois sommets centraux, l'un des 27 sommets extérieurs ne peut être coloré, ce qui montre que le nombre chromatique de liste de K 3,27 est au moins quatre. En théorie des graphes, la coloration de liste est une coloration des sommets d'un graphe où la couleur de chaque sommet est restreinte à une liste de couleurs autorisées.
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges (from the original graph) connecting pairs of vertices in that subset. Formally, let be any graph, and let be any subset of vertices of G. Then the induced subgraph is the graph whose vertex set is and whose edge set consists of all of the edges in that have both endpoints in . That is, for any two vertices , and are adjacent in if and only if they are adjacent in .
frame|right|Le graphe de Petersen, à gauche et son complémentaire, à droite. En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple est un graphe simple ayant les mêmes sommets et tel que deux sommets distincts de soient adjacents si et seulement s'ils ne sont pas adjacents dans . Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé. Le complémentaire du complémentaire est le graphe original.
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.
vignette|Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe. Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins. alt=A small example network with 8 vertices and 10 edges.|vignette|Réseau de huit sommets (dont un isolé) et 10 arêtes.
thumb|Exemple de graphe possédant une 3-clique (en rouge) : les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux. thumb|Exemple de « biclique » : le graphe biparti complet K3,3. Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. Une clique maximum d'un graphe est une clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets).
thumb|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.
