# The topology of competitively constructed graphs

- Published in 2013
- Added on

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.

## Links

## 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} }