The topology of competitively constructed graphs

2013-01-15T00:00:00Z (GMT) by Alan Frieze Wesley Pegden

We consider a simple game, the k-regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices cannot exceed k. We show a sharp topological threshold for this game: for the case k = 3 a player can ensure the resulting graph is planar, while for the case k = 4, a player can force the appearance of arbitrarily large clique minors.