Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract: The Strong Perfect Graph Conjecture is a famous conjecture stated in the early sixties. It is known that a minimal counter example to this conjecture would be a partitionable graph. In 1999, Boros, Gurvich and Hougardy proved that a graph is partitionable if and only if it is partitionable with respect to its maximum cliques, introducing thereby the concept of partitionable families.

In this talk, we will focuse on "regular" partitionable families, that is partitionable families given by near-factorizations of finite groups. The characterization of near-factorization of cyclic groups is an open problem for now more than fifteen years. Little is known about near-factorizations of non-cyclic groups: we will present a software designed to look for near-factorizations in any finite group of small order. Computations revealed the smallest and first group with near-factorizations, which is not cyclic and not dihedral.