Evènement pour le groupe
GT Graphes et Applications
Date | 2016-03-04 14:00-15:00 |
Titre | The coloring problem in graphs with structural restrictions |
Résumé | Graph coloring is an NP-complete problem in general. Even for a fixed k >= 3 and for a fixed graph H that is not a collection of paths, deciding whether a graph with no induced copy of H is k-colorable is NP-hard. Here we consider the case where H is a path on six vertices. Whether 4-coloring graphs with no induced path on six vertices can be decided in polynomial time remains an open question. We answer positively in the restricted setting of bull-free graphs, through structural observations that lead to a polynomial algorithm. This is joint-work with Frédéric Maffray. |
Lieu | Salle 178 |
Orateur | Lucas Pastor |
Aucun document lié à cet événement.
RetourRetour à l'index