2

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

Stefan Kohl
  • 19,498
  • 21
  • 73
  • 136
Tom
  • 21
  • What do you have in mind when you say "important"? can you expand on your motivation – Yemon Choi Jan 31 '12 at 07:44
  • 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. – nvcleemp Jan 31 '12 at 08:35
  • 2
    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. – Johan Wästlund Jan 31 '12 at 09:25

2 Answers2

3

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.

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
1

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

xinli0
  • 11