3
$\begingroup$

I'm interested in either a formula or algorithm for figuring out the number of graphs of size $n$ which have a given graph as a minor. Are there any results regarding this?

$\endgroup$
  • $\begingroup$ I'm sure you've thought of the obvious algorithm with horrific time complexity. I'm sure one could do better than that, but I would bet not much better. $\endgroup$ – Matt Samuel Feb 16 '16 at 2:20
  • $\begingroup$ Yes. I'd be disappointed if the only algorithm was "enumerate all the graphs of size n", as it doesn't give any insight into the problem. $\endgroup$ – Davis Yoshida Feb 16 '16 at 2:27
  • $\begingroup$ Mathoverflow might be a better place to ask this. I think this qualifies as research level combinatorics. $\endgroup$ – Matt Samuel Feb 16 '16 at 2:28
  • $\begingroup$ I'm not really a research level mathematician, so I don't usually post there. $\endgroup$ – Davis Yoshida Feb 16 '16 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.