INF568A : Graphes et Applications (3 ECTS)

au semestre 3

Code apogé

INF568A

Organisateur

Master d'informatique

Rédacteurs

Prérequis

Théorie des Graphes et Recherche Opérationnelle (INF473)

Publique

spécialité 3, master info

Mots clés

coloration

Objectifs

Ce cours a pour objet de présenter des notions acancées de la théorie des graphes et de familiariser l'étudiant avec des techniques de preuves classiques en prenant appui sur des problèmes de coloration de graphes.

Programme détaillé

  

• 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é
• 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