التمرين 1
Exercice 1 — QCM sur les graphes parfaits et la coloration
#perfect-graphs#graph-coloring#graph-classes
- Un graphe planaire de Berge est-il parfait, faiblement parfait, imparfait critique ou quatre-coloriable ?
- Pour les graphes quasi localement sans patte, la reconnaissance ou le calcul du nombre chromatique sont-ils polynomiaux, NP-complets ou ouverts ?
- Lors de la contraction de deux sommets non adjacents, comment varie le nombre chromatique et l’extension d’une coloration est-elle polynomiale ?
- Dans un graphe où les arêtes relient des signaux facilement distinguables, quel objet représente un plus grand ensemble de signaux deux à deux distinguables ?
- Un trou est-il localement scindé, localement triangulé, localement parfait ou faiblement parfait ?
◀الحل
1.
Un graphe de Berge est parfait. S’il est planaire, il est aussi quatre-coloriable.
2.
La réponse dépend de la définition exacte de la classe utilisée dans le cours.
3.
Toute coloration du graphe contracté s’étend en temps polynomial.
4.
5.
Un trou est un cycle induit de longueur au moins ; un trou impair n’est pas parfait.