One of the difficulties of obtaining a new result in graph theory has been finding the statement of the result. This situation may soon change as computers are now capable of generating interesting mathematical conjectures. A conjecture generating program, called Graffiti, was developed by Siemion Fajtlowicz in 1986 at the University of Houston, Texas. It uses a database of graphs and heuristically checks for relationships among certain graph invariants. The main task of the program is to decide which of these relationships should be accepted as conjectures.
Having obtained a readily available computer tape of all the nonisomorphic graphs with 10 or fewer vertices, we have tested over 200 of the Graffiti conjectures and have found counterexamples for several of them (and a few proofs). Our Graffiti research is summerized in the following two papers.
Tony L. Brewster and Michael J. Dinneen and Vance Faber, ``A Computational Attack on the Conjectures of Graffiti: New Counterexamples and Proofs'' , Discrete Mathematics, 147(1-3):35--55, 1995.
Michael J. Dinneen, ``A Computational Attack on Graffiti's Matching and Chromatic Number Conjectures'' , Los Alamos National Laboratory manuscript (1992).
For related papers on the conjectures of Graffiti see Ermelinda DeLaVina's Graffiti page.