Unfriendly partition of graphs without an infinite subdivided clique

Unfriendly partition of graphs without an infinite subdivided clique

-
Eli Berger, University of Haifa
Fine Hall 224

In this talk I prove that every graph with less than $\aleph_\omega$ vertices, which does not contain a subdivision of an infinite clique as a subgraph, must have a partition of its vertices to two sets, so that no vertex has more neighbors in its own set than in the other set. The proof uses the theorem given by Robertson Seymour and Thomas (http://www.ams.org/mathscinet/pdf/1079057.pdf), saying that such a graph has a tree decomposition with certain properties. The unfriendly partition is then constructed by analyzing some infinite game played on this tree.