Automated generation of conjectures on forbidden subgraph characterization
详细信息 查看全文
- 作者：Christian Desrosiers ; Philippe Galinier ; Pierre Hansen ; Alain Hertz
- 关键词：Graph theory ; Forbidden subgraph characterization ; Automated conjecture generation
- 刊名：Discrete Applied Mathematics
- 出版年：10 January, 2014
- 年：2014
- 卷：162
- 期：Complete
- 页码：177-194
- 全文大小：932 K
文摘
Given a class of graphs , a forbidden subgraph characterization (FSC) is a set of graphs such that a graph belongs to if and only if no graph of is isomorphic to an induced subgraph of . 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. Since most classes of graphs do not have such characterization, we also describe methods to find less restrictive results in the form of necessary or sufficient conditions to characterize a class of graphs with forbidden subgraphs. Furthermore, while these methods require to explore a possibly infinite search space, we present an enumerative technique that guarantees the discovery of characterizations involving forbidden subgraphs with a limited number of vertices. Another technique, which enables the discovery of characterizations with much larger subgraphs through the use of a heuristic search, is also described. In our experiments, we use these methods to find new theorems on the characterization of well-known graph classes.