Abstract :
[fr] Dans les 60 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.
[en] In the last 60 years, polyominoes have been the object of many investigations. A central problem, that is still open, is to determine the number of polyominoes with n square cells. An approach to solve the problem is to use a combinatorial description of polyominoes and to try to describe particular families of polyominoes. Behind each polyomino there is a graph whose vertices are the cells, such that two vertices are adjacent if their cells share a common edge. In this framework, one can study the polyominoes with an acyclic graph, called tree-like polyominoes. In 2016, Blondin-Massé et al. determined the maximal number that can have a tree-like polyomino with n cells. In this talk, we generalize this problem to graphs in general and we show this problem is NP-complete. However, the problem becomes polynomial when we restrict ourselves to trees or to graphs with a constant tree-width.
