Voir la source de Graphe parfait

{{Ébauche|mathématiques}}
[[Image:Paley9-perfect.svg|vignette|Graphe parfait avec une clique de trois sommets.]]
En [[théorie des graphes]], le '''graphe parfait''' est une notion introduite par [[Claude Berge]] en 1960. Il s'agit d'un graphe pour lequel le [[Coloration de graphe#Définition (nombre chromatique)|nombre chromatique]] de chaque [[sous-graphe induit]] et la taille de la plus grande [[clique (théorie des graphes)|clique]] dudit sous-graphe induit sont égaux.

Un graphe <math>G</math> est '''1-parfait'''<ref>{{lien conférence
  |auteur = Coudert, Olivier
  | année = 1997
  | titre = Exact Coloring of Real-Life Graphs is Easy
  | pages = 121–12
  | éditeur = DAC '97: Proceedings of the 34th annual Design Automation Conference 
  | doi = 10.1145/266021.266047 | doi-access = free }}</ref> si son [[nombre chromatique]] (noté <math>\chi(G)</math>) est égal à la taille de sa plus grande clique (notée <math>\omega(G)</math>) : <math>\chi(G)=\omega(G)</math>. 
Dans ce cas, <math>G</math> est parfait si et seulement si tous les sous graphes de <math>G</math> sont 1-parfait.

== Intérêt ==
Depuis la formulation des conjectures jusqu'à la démonstration du théorème ''fort'', l'intérêt pour les graphes parfaits n'a cessé de croître. Il n'est pas retombé non plus après la publication de la preuve puisque la très grande technicité et la longueur de celle-ci laissent espérer l'existence d'une preuve plus courte et qui en renforce la compréhension.

Les deux principales motivations, en dehors de la théorie des graphes, pour l'étude des graphes parfaits sont d'ordres [[polyèdre|polyédrique]] et [[algorithmique]]. Ceci tient notamment à l'existence d'une autre définition équivalente d'un graphe parfait due à [[Václav Chvátal]]<ref>{{article|langue=en|prénom=Václav|nom=Chvátal|titre=On certain polytopes associated with graphs|lien périodique=Journal of Combinatorial Theory|revue={{abréviation|JCTB|Journal of Combinatorial Theory, Series B}}|vol=18|année=1975|p.=138-154}}.</ref> :
{{citation bloc|Un graphe est parfait si et seulement si son [[polytope des stables]] est défini par les [[contraintes de clique]].}}
Partant de ce résultat, [[Martin Grötschel]], [[László Lovász]] et [[Alexander Schrijver]] montrent que dans les graphes parfaits on peut résoudre en temps polynomial le [[coloration de graphe|problème de la coloration de graphe]]<ref>{{Ouvrage|langue=en|prénom1=Martin|nom1=Grötschel|prénom2=László|nom2=Lovász|prénom3=Alexander|nom3=Schrijver|titre=Geometric algorithms and combinatorial optimization|éditeur=[[Springer Verlag|Springer]]|année=1988|pages totales=362|isbn=0-387-13624-X}} et ({{2e}} éd. corrigée, 1993) {{ISBN|978-0-387-56740-2}}.</ref>, équivalant au problème de la recherche du [[ensemble stable de poids maximal|stable maximum]] et aussi au problème de la recherche de la clique maximum, par le théorème faible.

== Théorèmes ==
{{article détaillé|Théorème des graphes parfaits}}
Claude Berge a émis deux conjectures caractérisant ces graphes parfaits. Elles ont été démontrées en [[1972 en science|1972]] et [[2002 en science|2002]] et sont devenues des théorèmes.

=== Théorème ''faible'' des graphes parfaits ===
{{théorème|énoncé=Un graphe est parfait si et seulement si son [[graphe complémentaire|complémentaire]] est parfait.}}

Cette conjecture a été démontrée en 1972 par
[[László Lovász]]<ref>{{article|langue=en|nom=Lovász|prénom=László|doi=10.1016/0012-365X(72)90006-4|lien périodique=Liste des journaux scientifiques en mathématiques#D|revue=Discrete Math.|p.=253-267|titre=Normal hypergraphs and the perfect graph conjecture|vol=2|année=1972|numéro=3}}.</ref>.

=== Théorème ''fort'' des graphes parfaits ===
{{théorème|énoncé = Un graphe est parfait si et seulement si ni lui ni son complémentaire ne contiennent de [[cycle (graphe)|cycle]] ''impair'' induit de longueur au moins cinq}}

Cette conjecture a été démontrée en 2002 par [[Maria Chudnovsky]], [[Neil Robertson (mathématicien)|Neil Robertson]], [[Paul Seymour (mathématicien)|Paul Seymour]] et [[Robin Thomas (mathématicien)|Robin Thomas]].

=== Remarque ===
 
Le théorème fort implique trivialement le théorème faible. De fait on parle du « [[théorème des graphes parfaits]] » en désignant implicitement le théorème ''fort''.

== Classes de graphes parfaits ==
Les graphes suivants sont des graphes parfaits : les [[graphe biparti|graphes bipartis]], les [[line graph|line graphs]], les [[graphe de permutation|graphes de permutations]] et les [[graphe cordal|graphes cordaux]], en particulier les [[Graphe scindé|graphes scindés]], les [[Graphe ptolémaïque|graphes ptolémaïques]], les [[Graphe à distance héréditaire|graphes à distance héréditaire]].

== Notes et références ==
{{Références|taille=30}}

== Voir aussi ==
=== Bibliographie ===

* Claude Berge, ''Graphes et hypergraphes'', [[Éditions Dunod|Dunod]], {{2e|{{éd.}}}}, 1973 {{ISBN|2-04-016906-7}} (en particulier, {{nobr|chapitre 16}} sur les graphes parfaits)
* Claude Berge, ''Graphes'', [[Gauthier-Villars]], {{3e|{{éd.}}}}, 1983 {{ISBN|2-04-015555-4}}
<!-- Remarque : 
il manquerait une belle référence à un ouvrage ou article sélectionné de Claude Berge ! 
-->
* {{en}} [[Maria Chudnovsky]], [[Neil Robertson (mathématicien)|Neil Robertson]], [[Paul Seymour (mathématicien)|Paul D. Seymour]] et [[Robin Thomas (mathématicien)|Robin Thomas]], « Progress on perfect graphs », dans ''Math. Programming'' Ser. B, {{vol.|97}}, 2003, {{p.| 405-422}}, [http://www.math.gatech.edu/~thomas/PAP/perfsur.pdf PDF]
<!-- Exemplaire PDF de l'article synthétique (22 pages, 2003) sur CiteSeer : 
http://citeseer.ist.psu.edu/cache/papers/cs/27424/http:zSzzSzcgi.di.uoa.grzSz~teleliszSzstaffzSzperfsur.pdf/chudnovsky02progress.pdf 
-->
<!-- Exemplaire PDF de l'article initial (148 pages, 2002) : (page de Robin Thomas, co-auteur) 
http://www.math.gatech.edu/~thomas/PAP/ 
http://www.math.gatech.edu/~thomas/PAP/spgc.pdf 
-->
<!-- Voir aussi la page de Vašek Chvátal : 
http://www.cs.concordia.ca/~chvatal/perfect/problems.html 
-->

=== Articles connexes ===
* [[Théorème de Dilworth]]
* [[Théorème d'Erdős-Szekeres]]
* {{Lien|langue=en|trad=Mirsky's theorem|fr=Théorème de Mirsky}}

=== Lien externe ===
* {{lien web|url=https://www.quantamagazine.org/20151020-perfect-graph-coloring/#st_refDomain=11011110.livejournal.com&st_refQuery=/|titre=Theorists Draw Closer to Perfect Coloring|auteur=Natalie Wolchover |date= 20 octobre 2015 |site=QuantaMagazine}}

{{Portail|mathématiques|informatique théorique}}

{{DEFAULTSORT:Graphe parfait}}
[[Catégorie:Graphe parfait|*]]
[[Catégorie:Théorème de la théorie des graphes|graphes parfaits, theoreme des]]
[[Catégorie:Conjecture démontrée]]