Groupe d’études et de recherche en analyse des décisions

# Automated Generation of Conjectures on Forbidden Subgraph Characterization

## Christian Desrosiers, Philippe Galinier, Pierre Hansen et Alain Hertz

Given a class of graphs $\mathcal{F}$, a forbidden subgraph characterization (FSC) is a set of graphs $\mathcal{H}$ such that a graph G belongs to $\mathcal{F}$ if and only if no graph of $\mathcal{H}$ is isomorphic to an induced subgraph of G. FSCs play a key role in graph theory, and are at the center of many important results obtained in that field. In this paper, we present novel methods that automate the generation of conjectures on FSCs, or conditions to have an FSC. We also use these methods to reproduce some known results of graph theory, as well as to discover new ones.

, 29 pages