Sous-arbres induits pleinement feuillus : résultats de complexité

Dans les 30 dernières années, les polyominos ont été l'objet de nombreuses investigations. Un problème central, qui est pourtant toujours ouvert, est de déterminer le nombre de polyominos à n cellules carrées. Une approche possible de ce problème est d'utiliser une description combinatoire. Derrière chaque polyomino se cache un graphe dont les sommets correspondent aux cellules, tel que deux sommets sont adjacents si les cellules ont un côté en commun. Dans ce contexte, on peut étudier les polyominos dont le graphe est acyclique, appelés polyominos-arbres. En 2016, Blondin-Massé et al. ont déterminé le nombre maximal de feuilles que peut posséder un polyomino-arbre à n cellules. Dans cet exposé, nous généralisons ce problème aux graphes en général et nous montrons que le problème est NP-complet. Cependant, le problème devient polynomial lorsqu'on se restreint aux arbres et aux graphes de largeur arborescente constante.