What are some important conjectures in graph theory that have been checked by computer up to order 11?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What do you have in mind when you say "important"? can you expand on your motivation $\endgroup$– Yemon ChoiCommented Jan 31, 2012 at 7:44
-
$\begingroup$ And also, it is often not really necessary to check all graphs, since often it can be proven that the smallest counter example for a conjecture would be a graph with a special structure (e.g. snarks are known to be the smallest counter example for some conjectures if there would be a counter example) and so many conjectures have been checked up to a much higher order than 11. $\endgroup$– nvcleempCommented Jan 31, 2012 at 8:35
-
2$\begingroup$ What about those that have been checked up to order 10? Seriously, a good community wiki might be "What are some conjectures of the form 'Every graph that has property X also has property Y', and how far have they been checked?", along with a couple of examples of what you have in mind. In general, the prospects of good answers increase if some effort is put into the question. $\endgroup$– Johan WästlundCommented Jan 31, 2012 at 9:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Graffiti (by S. Fajtlowicz) and Graffiti.pc (by E. DeLaViña) are computer programs that produce conjectures in graph theory.
See Doug West's web page, "Some Conjectures of Graffiti.pc (2004-07)," and the more recent, "Bibliography on Conjectures, Methods and Applications of Graffiti," which includes papers through 2011.
$\begingroup$
$\endgroup$
I know one. The reconstruction conjecture of the undirected graph. That work is due to BD McKay.