Le théorème fort des graphes parfaits

Gérard Cornuéjols

Displaying similar documents to “Le théorème fort des graphes parfaits”

Les graphes de transfert et la notion de graphe inverse

Alain Leroux (1977)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Note sur une caractérisation des graphes dont le degré de déséquilibre est maximal

Ioan Tomescu (1973)

Mathématiques et Sciences Humaines

Similarity:

Dans cette note on démontre la conjecture d'Abelson et Rosenberg sur le degré maximal de déséquilibre d'un graphe à n sommets et on caractérise ces graphes maximaux.

Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille

Mustapha Aouchiche, Odile Favaron, Pierre Hansen (2009)

RAIRO - Operations Research

Similarity:

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme ${\underset{̲}{b}}_{n} \leq g \oplus i \leq {\bar{b}}_{n}$ où désigne la maille d'un graphe , un autre invariant parmi la distance moyenne $\bar{l}$ , l'index λ, l'indice de Randić et le nombre de domination , $\oplus$ désigne l'une des opérations +, -, ×, /, ${\underset{̲}{b}}_{n}$ et ${\bar{b}}_{n}$ des fonctions de l'ordre du graphe qui bornent l'expression $g \oplus i$ et sont atteintes pour tout (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

Coloration de graphes : fondements et applications

Dominique de Werra, Daniel Kobler (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Les modèles classiques de coloration doivent leur notoriété en grande partie à leurs applications à des problèmes de type emploi du temps ; nous présentons les concepts de base des colorations ainsi qu’une série de variations et de généralisations motivées par divers problèmes d’ordonnancement dont les élaborations d’horaires scolaires. Quelques algorithmes exacts et heuristiques seront présentés et nous esquisserons des méthodes basées sur la recherche Tabou pour trouver des solutions...

Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille

Mustapha Aouchiche, Pierre Hansen (2005)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d’illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme ${\underset{̲}{b}}_{n} \leq g \oplus i \leq {\bar{b}}_{n}$ où $g$ désigne la maille (ou longueur du plus petit cycle) du graphe $G = (V, E)$ , $i$ un autre invariant choisi parmi le nombre de...