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