The topology of competitively constructed graphs

MaRDI QIDQ405221zbMATH OpenFDO

Authors Wesley Pegden, Alan Frieze

Publication date 4 September 2014

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

Full work available at URL https://arxiv.org/abs/1312.0964, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p26

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

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)

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.

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

Cites work

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

Cited in

(3)

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

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)