Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

closed as not a real question by Bruce Westbury, Will Jagy, Ryan Budney, Chandan Singh Dalawat, Gerry Myerson Jan 31 '12 at 11:45

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
if you are just after a big list, then he question should be made community wiki. –  Yemon Choi Jan 31 '12 at 7:43
    
also, what do you have in mind when you say "important"? can you expand on your motivation –  Yemon Choi Jan 31 '12 at 7: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 8:35
1  
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 9:25

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

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