Section outline

    1. Coloration 
    2. Bornes et algorithmes 
    3. Coloration de graphes d’intervalles 
    4. Coloration de graphes planaires

    Coloring book (spikedmath.com)

    • Compétences

      1. Bornes et algorithmes
        • Connaitre les preuve sur les bornes de coloration avec la clique max et le degré max
        • Décrire l'algorithme glouton de coloration 
        • Utiliser l'algorithme glouton pour prouver la borne sur le degré max 
        • Modéliser des problèmes pratiques commme des problèmes de coloration de graphe 
      2. Graphes d'intervalles
        • Construire le graphe d'intersection associé à une famille d'ensembles 
        • Utiliser l'algorithme glouton pour résoudre optimalement la coloration de graphes d'intervalles 
        • Montrer l'optimalité de l'algorithme 
      3. Graphes planaires
        • Expliquer la formule d'Euler 
        • Démontrer qu'un graphe planaire est 6-coloriable 
        • Utiliser l'algorithme glouton pour 6-colorier un graphe planaire

      Vocabulaire : k -coloration, nombre chromatique, graphe d'intersection, graphe d'intervalles, graphe planaire

      Notations :  \chi(G) , \Delta(G) , \omega(G)

    • Transparents coloration File
      Students must
      View
    • Feuille d'exercices sur les graphes bipartis et la coloration File
      Students must
      Mark as done
    • One idea, one story: le théorème des 4 couleurs Page
      Students must
      View
    • Leçon sur la coloration de graphes Lesson
      Students must
      Mark as done
    • Modélisation de problèmes pratiques avec la coloration Lesson
      Students must
      Mark as done
    • Graphes planaires et coloration Lesson
      Students must
      Mark as done
    • Test Cliques, Stables et Coloration Quiz
      Students must
      View
      Receive a grade
      Receive a passing grade
    • Test graphes d'intervalles et graphes planaires Quiz
      Students must
      View
      Receive a grade
      Receive a passing grade