Evènement pour le groupe GT Graphes et Applications

Date 2016-03-04  14:00-15:00
TitreThe 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.  
LieuSalle 178 
OrateurLucas Pastor 

Aucun document lié à cet événement.

Retour à l'index