Is there a name for graphs with this property?

74 Views Asked by At

The property of the graph is the following: it's countable, undirected, simple, and for any infinite subset of vertices there are two vertices connected(by infinite Ramsey theorem this is in fact equivalent to that any infinite induced subgraph contains an infinite complete graph).

Is there a name for this kind of graphs? Moreover, do we have a structure theorem for them?

1

There are 1 best solutions below

0
On

"Graphs with no infinite independent set" seems reasonably concise to me.

As a proof of concept, using that as a search term found me this paper, which proves a sort of structure theorem:

If a countable undirected graph has no infinite independent set, then it has a spanning subgraph which is the comparability graph of a poset with no infinite antichain.

The reverse implication also holds, since an independent set in a comparability graph is the same as an antichain in the poset, so this characterizes the minimal countable graphs with no infinite independent set.

Of course, you may then ask "Is there a structure theorem for posets with no infinite antichain?" Seaching for posets with no infinite antichain found me this result.