Retour

G-2007-48

Automated Generation of Conjectures on Forbidden Subgraph Characterization

, , et

référence BibTeX

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

Axe de recherche

Applications de recherche

Publication

, , et
Discrete Applied Mathematics, 162, 177–194, 2014 référence BibTeX