The topology of competitively constructed graphs

zbMATH Open1300.05076arXiv1312.0964MaRDI QIDQ405221FDOQ405221

Authors: Wesley Pegden, Alan Frieze 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1312.0964

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the Hamiltonicity of the \(k\)-regular graph game
• Planarity, Colorability, and Minor Games
• How long can a graph be kept planar?
• The isolation game for regular graphs
• A simple competitive graph coloring algorithm. III

zbMATH Keywords

combinatorial gamesgraph minorsplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57) Graph minors (05C83) Games involving graphs (91A43) Combinatorial games (91A46)

Cites Work

• A kuratowski theorem for the projective plane
• Combinatorial Games
• Cubic irreducible graphs for the projective plane

Cited In (3)

• A random variant of the game of plates and olives
• STACS 2004
• On the Hamiltonicity of the \(k\)-regular graph game

This page was built for publication: The topology of competitively constructed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405221)