Concept
Coloration de graphe
Concepts associés (77)
Polynôme de Tutte
Le polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. L'importance de ce polynôme provient des informations qu'il contient sur le graphe .
Théorème de Vizing
Le théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Il est dû à Vadim G. Vizing. 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. On note χ′(G) le nombre minimum de couleur nécessaire pour avoir une coloration des arêtes.
Coloration de liste
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.
Nombre achromatique
En théorie des graphes, une coloration complète est l'opposé d'une coloration harmonieuse en ce sens que c'est une coloration des sommets dans laquelle toute paire de couleurs apparait au moins sur une paire de sommets adjacents. Le nombre achromatique ψ(G) d'un graphe G est le nombre maximum de couleurs possibles dans une coloration complète de G. right|300px|thumb|Coloration complète du graphe de Clebsch avec 8 couleurs. Dans la figure ci-contre, on a réussi à colorier le graphe de Clebsch avec huit couleurs, de manière que chaque paire de couleurs apparaisse sur au moins une arête.
Acyclic coloring
In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number A(G) of a graph G is the fewest colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. A(G) ≤ 2 if and only if G is acyclic. Bounds on A(G) in terms of Δ(G), the maximum degree of G, include the following: A(G) ≤ 4 if Δ(G) = 3. A(G) ≤ 5 if Δ(G) = 4. A(G) ≤ 7 if Δ(G) = 5. A(G) ≤ 12 if Δ(G) = 6.
Théorie algébrique des graphes
vignette|Le graphe de Petersen, qui possède 10 sommets et 15 arêtes. Hautement symétrique, il est en particulier distance-transitif. Son groupe d'automorphisme a 120 éléments et est en fait le groupe symétrique S. De diamètre 2, il possède 3 valeurs propres. En mathématiques, la théorie algébrique des graphes utilise des méthodes algébriques pour résoudre des problèmes liés aux graphes, par opposition à des approches géométriques, combinatoires ou algorithmiques.
Graphe arête-transitif
vignette|Graphe de Gray, arête-transitif et régulier mais pas sommet-transitif. En théorie des graphes, un graphe non-orienté est arête-transitif si pour tout couple d'arêtes, il existe un automorphisme de graphe envoyant la première arête sur la seconde. Un graphe non-orienté est arête-transitif si pour tout couple d'arêtes, il existe un automorphisme de graphe envoyant la première arête sur la seconde. En d'autres termes, un graphe est arête-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arêtes.
Théorème des graphes parfaits
En mathématiques, et plus précisément en théorie des graphes, le théorème des graphes parfaits (parfois appelé théorème fort des graphes parfaits) est une caractérisation des graphes parfaits par certains sous-graphes , conjecturée par Claude Berge en 1961. Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas en annoncèrent la démonstration en 2002, et la publièrent en 2006. Elle valut à leurs auteurs le prix Fulkerson de 2009.
Graphe de Grötzsch
Le graphe de Grötzsch est, en théorie des graphes, un graphe possédant 11 sommets et 20 arêtes. C'est le plus petit graphe sans triangle de nombre chromatique 4. Il est nommé d'après Herbert Grötzsch qui l'a découvert en 1958. 480px|Construction du graphe de Grötzsch.140px|Le résultat. Le graphe de Grötsch peut être vu comme le graphe de Mycielski construit à partir du graphe cycle à cinq sommets : pour chaque sommet du graphe cycle, on crée un nouveau sommet lié aux deux voisins de ; on crée ensuite un nouveau sommet lié à tous les .
Graphe roue
En théorie des graphes, le graphe roue Wn est un graphe d'ordre formé en ajoutant un sommet « centre » connecté à tous les sommets du graphe cycle Cn-1. La notation Wn provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent Wn-1, faisant référence à la longueur du cycle. Pour les valeurs impaires de n, le graphe Wn est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue Wn n'est pas parfait.