### On the order of countable graphs

by Nesetril and Shelah. [NeSh:745]

European J Combinatorics, 2003

A set of graphs is said to be independent if there is no
homomorphism between distinct graphs from the set. We consider the
existence problems related to the independent sets of countable
graphs. While the maximal size of an independent set of countable
graphs is 2^omega the On Line problem of extending an
independent set to a larger independent set is much harder. We prove
here that singletons can be extended (``partnership
theorem''). While this is the best possible in general, we give
structural conditions which guarantee independent extensions of
larger independent sets. This is related to universal graphs, rigid
graphs and to the density problem for countable graphs.

Back to the list of publications