Back

G-2002-46

What Forms Do Interesting Conjectures Have in Graph Theory?

, , , , and

BibTeX reference

Conjectures in graph theory have multiple forms and involve graph invariants, graph classes, subgraphs, minors and other concepts in premisses and/or conclusions. Various abstract criteria have been proposed in order to find interesting ones with computer-aided or automated systems for conjecture-making. Beginning with the observation that famous theorems (and others) have first been conjectures, if only in the minds of those who obtained them, we review forms that they take. We also give examples of conjectures of such forms obtained with the help of, or by, computers when it is the case. It appears that many forms are unexplored and so computer-assisted and automated conjecture-making in graph theory, despite many successes, is pretty much at its beginning.

, 32 pages

This cahier was revised in June 2004

Research Axes

Research applications

Publication

What forms do interesting conjectures have in graph theory?
, , , , and
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 69, 231–252, 2005 BibTeX reference