# The topology of competitively constructed graphs

• Published in 2013
In the collections
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.

## Other information

pages
9

### BibTeX entry

@article{Frieze2013,
title = {The topology of competitively constructed graphs},
author = {Frieze, Alan and Pegden, Wesley},
url = {http://arxiv.org/abs/1312.0964 http://arxiv.org/pdf/1312.0964v2},
urldate = {2013-12-30},
abstract = {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.},
comment = {},
month = {dec},
pages = 9,
year = 2013,
archivePrefix = {arXiv},
eprint = {1312.0964},
primaryClass = {math.CO},
collections = {Games to play with friends,Protocols and strategies}
}