Syllabus 2013/2014
 
Extrait PDF Anglais
Français
index
Module : IF307
Titre :
Enseignement Master Recherche
Volumes horaires :
Cours : 24.00 h
Travail Individuel : 48.00 h
Crédits ECTS :
2.50
Enseignant(s) :
MOSBAH Mohamed - Responsable
ZEMMARI Akka
Niveau :
module de troisième année
Résumé :
Ce cours a pour objectif de présenter des notions avancées de théorie des graphes et de familiariser l'étudiant avec certaines techniques de preuve classiques en prenant appui sur des problèmes de coloration de graphes.
Plan :
  1. Première partie (Éric Sopena)
    • Coloration de graphes
      • Définitions de base
      • Résultats de base
      • Graphes planaires
      • Graphes critiques
      • Graphes parfaits
      • Polynômes chromatiques
    • Homomorphismes de graphes
      • Homomorphismes et colorations
      • Hiérarchie des classes de coloration
      • Problème de la H-coloriabilité
  2. Deuxième partie (André Raspaud)
    • Colorations particulières
      • Coloration fractionnaire
      • Coloration circulaire
      • Coloration par liste
    • Dualité
      • Flots à valeurs entières
      • Flots circulaires
    • Colorations et applications
      • Coloration totale
      • L(2,1)-étiquetage
Prérequis :
Notions élémentaires de théorie des graphes.
Document(s) :
Béla Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer (1998), Chap. V : Colouring, pp. 145-180.

Claude Berge, Graphes et hypergraphes, Dunod, 2ème édition (1973), Chap. 15 : Nombre chromatique, pp. 314-346, Chap. 16 : Graphes parfaits, pp. 347-370, Chap. 12 : Indice chromatique, pp. 236-259.

Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization (1995).

Roy Nelson and Robin J. Wilson (Eds), Graph Colourings, Pitman Research Notes in Mathematics Series 218, Longman (1990).

Bjarne Toft, Colouring, stable sets and perfect graphs, in Handbook of Combinatorics, vol. I (Graham, Grötschel and Lovász eds), North-Holland (1995), pp. 233-288.

Mot(s) clé(s) :
Algorithmique de graphes, coloration.