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.
@article{10_37236_3942,
author = {Alan Frieze and Wesley Pegden},
title = {The topology of competitively constructed graphs},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/3942},
zbl = {1300.05076},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3942/}
}
TY - JOUR
AU - Alan Frieze
AU - Wesley Pegden
TI - The topology of competitively constructed graphs
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/3942/
DO - 10.37236/3942
ID - 10_37236_3942
ER -
%0 Journal Article
%A Alan Frieze
%A Wesley Pegden
%T The topology of competitively constructed graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3942/
%R 10.37236/3942
%F 10_37236_3942
Alan Frieze; Wesley Pegden. The topology of competitively constructed graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3942
