MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

9 added 18 characters in body; [made Community Wiki]

As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.

I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.

There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:

M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.

B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.

8 deleted 18 characters in body

As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.

I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.

There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:

M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.

B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.

7 added 16 characters in body

As others have mentioned, the answer to your title question is strictly speaking no. HoweverWith regards to your other questions, I will remark that it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.

I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.

There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:

M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.

B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.

6 edited body
5 added 81 characters in body
4 added 322 characters in body; added 19 characters in body; added 1 characters in body
3 added 493 characters in body
2 deleted 238 characters in body
1