Are there arbitrary size families of non-comparable graphs under the minor relationship?

31 Views Asked by At

A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from $G$ by means of vertex- and edge-deletion as well as edge-contraction.

Robert-Seymour theorem states that any infinite family of (finite) graphs contains a pair of graphs such that one is a minor of the other.

The question is, given an arbitrarily large integer $k$, is there a family of at least $k$ (finite) graphs such that none of them is a minor of another one?

In case of an affirmative answer, could you give a construction for such families?

1

There are 1 best solutions below

1
On BEST ANSWER

Yes: take $k$ non-isomorphic graphs with the same number of vertices and edges.