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

G-2007-48

Automated Generation of Conjectures on Forbidden Subgraph Characterization

, , et

Given a class of graphs , a forbidden subgraph characterization (FSC) is a set of graphs such that a graph G belongs to if and only if no graph of 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