Graphes parfaits
TBD def
TBD différence non bornée : https://perso.ens-lyon.fr/edouard.bonnet/publi/tree-zykov.pdf et https://math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/Zhang.pdf TBD dessins de quelques graphes parfait
NP complet en general mais poly en perfect graphs : https://www.graphclasses.org/classes/gc_56.html et https://en.wikipedia.org/wiki/Perfect_graph#Algorithms
On en connaît déjà :
- les cliques et les chemins de longueur pair
- graphes biparti (donc les arbres)
Et il y en a plein d'autres :
- graphes cordées (https://math.stackexchange.com/questions/4045122/why-are-chordal-graphs-always-perfect-graphs), donc aussi les graphes d'intervalles
- graphes de comparabilités
- ...
TBD exo : Threshold graphs are perfect : https://en.wikipedia.org/wiki/Threshold_graph
Il existe deux types d graphes fondamentaux qui ne sont pas parfait les cycles de longueur impair $C_{2p+1}$ avec $p>1$ - nommés odd holes - et leurs complémentaires $\overline{C_{2p+1}}$, nommés odd antiholes :
Montrez que les graphes $C_{2p+1}$ et $\overline{C_{2p+1}}$ ne sont pas parfaits.
corrigé
corrigé
On a vu que $\omega(C_{2p+1}) = 2 < \chi(C_{2p+1}) = 3$.
Pour les $\overline{C_{2p+1}}$, il suffit de remarquer que :
- $\omega(\overline{C_{2p+1}}) = p$ puisque $\{x_{2i+1} \vert 0\leq i \leq p\}$ est une clique et tout sous ensemble à $p+1$ sommet contiendra forcément 2 voisins (principe ds tiroirs)
- $\chi(\overline{C_{2p+1}}) = p+1$ car $c(x_i)$ ne peut être au mieux égale qu'à 1 seul de ses voisins ($\chi(\overline{C_{2p+1}}) \geq p+1$) et la coloration $c(x_{1})=0$ et $c(x_{2i}) = c(x_{2i+1}) = i$ pour $1\leq i \leq p$ fonctionne.
TBD exercice les cycles non cordés de longueur impair (odd holes) ne sont pas des graphes parfais, ainsi que leurs complémentaires (anti odd holes), en déduire que tout graphe qui possède un cycle impair non cordé ou son complémentaire ne peut-être parfait.
Les graphes parfait lient également les cliques et les stables :
Proposition
Un graphe $G$est parfait si et seulement pour tout sous graphe $H$ de $G$ à $V(H)$ sommets, on a $\omega(H)\alpha(H)> V(H)$
preuve
preuve
TBD thm 3.1 https://ahmadabdi.com/ltcc/lecture_2.pdf
Théorème (Lovàsz, 1972)
Un graphe est parfait si et seulement si son complémentaire est parfait.
preuve
preuve
TBD
Conséquence directe de la proposition précédente en remarquant que $\omega(G) = \alpha(\overline{G})$.
Strong Perfect Graph Theorem (179 pages sans un seul dessin)
Le théorème fort des graphes parfait permet de faire des algorithmes de reconnaissance polynomiaux : https://algorithms.leeds.ac.uk/wp-content/uploads/sites/117/2017/09/FOCS03final.pdf
On les retrouves à des endroits inattendus :
TBD le line graph d'un graphe biparti est parfait. TBD graphe auto complémentaire parfait : https://mathoverflow.net/questions/452045/are-there-many-self-complementary-perfect-graphs TBD problèmes de coloration facile du coup : https://iuuk.mff.cuni.cz/~rakdver/kgii/lesson20-8.pdf