Chapitre 1 - Coloration de graphes

1. Définitions
• notation V(G), E(G), n(G), m(G)
  
• k-coloration
• nombre chromatique χ
  
• cas des arbres, cycles C_2n et C_2n+1, graphes complets K_n
• complexité
• invariants :
  
• cardinal maximum d'un stable α
  
• cardinal maximum d'une clique ω
• degré maximum Δ
  
2. Encadrement
   
• Algorithme glouton "First Fit"
• Δ(G) + 1 ≥ χ(G) ≥ max(ω(G), n(G)/α(G))
  
3. Théorème de Brooks
• Rappel  : notion de connexité
• Enoncé
• Preuve de Lovász

• Fin de la preuve du théorème de Brooks

Chapitre 2 - Graphes parfaits

1. Définitions
• couverture de clique
  
• α(G) ≤ k(G) et χ(G) = k(Ḡ) (Ḡ = complémentaire de G)
2. Graphes parfaits
• définition
• exemples
• propriété "duale": G parfait ssi Ḡ satisfait : pour tout S sous-ensemble de V(Ḡ), α(Ḡ_S) = k(Ḡ_S)
• Théorème de Lovász (conjecture faible de Berge) : G est parfait ssi Ḡ est parfait.
• Théorème de Lovász : Si G est parfait et soit x un sommet de G, alors le graphe obtenu en remplaçant x par une clique et en reliant chaque sommet de la clique aux voisins de x dans G est parfait.
  

  ---

  Théorème : G est parfait ssi pour tout G' sous-graphe induit de G, ω(G')ω(Ḡ') ≥ n(G')
• Théorème de Robertson, Seymour, Chudnovsky, Thomas (conjecture forte de Berge) : G est parfait ssi ni lui ni son complémentaire ne contiennent de cycle de longueur impaire supérieure ou égale à 5 comme sous-graphe induit.
  
3. Caractérisation polyhédrale des graphes parfaits
• Théorème (Chvátal) : Soit A une matrice de cliques d'un graphe G, G est parfait ssi P_I(A) = P(A).

Chapitre 3 - Graphes triangulés

1. Définition
• Graphe triangulé
• Exemples
  
• Séparateur
• Théorème : dans un graphe triangulé, tout séparateur minimal est une clique
2. Sommet simplicial et élimination simpliciale
• Définition
  
• Théorème : tout graphe G triangulé possède un sommet simplicial et si G n'est pas une clique, il en possède au moins deux non adjacents.
• Ordre d'élimination simplicial
• Théorème : G est triangulé si et seulement si il possède un ordre d'élimination simplicial
  
3. Parcours en largeur lexicographique (LexBFS)
• Enoncé
• Exemple
• Théorème : Un graphe G est triangulé ssi l'algorithme LexBFS donne un ordre d'élimination simplicial sur G
• Exercices tirés du DS 2019
• Théorème : les graphes triangulés sont parfaits (preuve TD4, exo 1)
  

Chapitre 4 - Graphes d'intervalles

1. Graphes d'intervalles
• définition
• exemple
• application
• Proposition : un sous-graphe induit d'un graphe d'intervalles est un graphe d'intervalles
• Proposition : un graphe d'intervalle est triangulé
2. Orientation transitive
• définition, graphe de comparabilité
• Proposition : le graphe complémentaire d'un graphe d'intervalle est de comparabilité
• Théorème : les 3 propositions suivantes sont équivalentes :
• G est un graphe d'intervalles
• G ne contient pas de cycle de longueur 4 sans corde et son complémentaire est un graphe de comparabilité
• Les cliques maximales de G peuvent être ordonnées de telle façon que pour tout sommet x, les cliques contenant x sont consécutives dans cet ordre.
• Corollaire : G est d'intervalles ssi G est triangulé et son complémentaire est de comparabilité

  ---

  Cours 5
  

  ---

3. Matrice de cliques
• propriété des 1-consécutifs pour les colonnes
  
• Théorème (Fulkerson) : un graphe G non orienté est un graphe d'intervalles ssi sa matrice des cliques maximales a la propriété des 1-consécutifs pour les colonnes
• Théorème : G est un graphe d'intervalles ssi
• G est un graphe triangulé
• tout ensemble de 3 sommets peut être ordonné tel que toute chaîne du premier au troisième passe par un voisin du second.
• Corollaire : G graphe d'intervalles ne contient pas le triplet astéroïde comme sous-graphe induit

Chapitre 5 - Graphes scindés (split-graphs)