The topology of competitively constructed graphs
type: Item
instance of: scholarly article
title: The topology of competitively constructed graphs
zbMATH Open document ID: 1300.05076
author: Wesley Pegden
author: Alan Frieze
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1312.0964
full work available at URL: v21i2p26
review text: Summary: 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.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C57
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A46
zbMATH DE Number: 6340193
zbMATH Keywords: combinatorial games
zbMATH Keywords: planar graphs
zbMATH Keywords: graph minors
MaRDI profile type: Publication
arXiv ID: 1312.0964
cites work: A kuratowski theorem for the projective plane
cites work: Combinatorial Games
cites work: Cubic irreducible graphs for the projective plane
description: scientific article; zbMATH DE number 6340193