The topology of competitively constructed graphs

• Published in 2013
• Added on 2013-12-30

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

• http://arxiv.org/abs/1312.0964
• http://arxiv.org/pdf/1312.0964v2

Other information

BibTeX entry

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