2
$\begingroup$

What are some important conjectures in graph theory that have been checked by computer up to order 11?

$\endgroup$
3
  • $\begingroup$ What do you have in mind when you say "important"? can you expand on your motivation $\endgroup$
    – Yemon Choi
    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$
    – nvcleemp
    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$ Jan 31, 2012 at 9:25

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I know one. The reconstruction conjecture of the undirected graph. That work is due to BD McKay.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.