Graphes (UGA)

Compétences

• 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 

• 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 

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

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