Building Spanning Trees Quickly in Maker-Breaker Games

DOI10.1137/140976054zbMath1331.91048arXiv1304.4108OpenAlexW1656969381MaRDI QIDQ2947437

Anita Liebenau, Dennis Clemens, Dan Hefetz, Asaf Ferber, Roman Glebov

Publication date: 23 September 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

positional gamesspanning treesmaker-breaker games

Mathematics Subject Classification ID

Trees (05C05) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (6)

Spanning trees of dense directed graphs ⋮ Generating random graphs in biased Maker-Breaker games ⋮ Strong Ramsey games: drawing on an infinite board ⋮ Fast strategies in Waiter-Client games ⋮ Hamiltonian Maker–Breaker Games on Small Graphs ⋮ Efficient Winning Strategies in Random‐Turn Maker–Breaker Games

Cites Work

• Unnamed Item
• Fast embedding of spanning trees in biased maker-breaker games
• Winning strong games through fast strategies for weak games
• The number of \(F\)-matchings in almost every tree is a zero residue
• On the clique-game
• On two problems regarding the Hamiltonian cycle game
• Ramsey games
• Positional games
• Weak and strong \(k\)-connectivity games
• Fast winning strategies in maker-breaker games
• On the maximum degree in a random tree
• Embedding Spanning Trees in Random Graphs
• Fast Strategies In Maker–Breaker Games Played on Random Boards
• Biased Positional Games
• On Biased Positional Games
• Deterministic Graph Games and a Probabilistic Intuition
• A Winning Strategy for the Ramsey Graph Game
• Proof of a Packing Conjecture of Bollobás
• Expanders Are Universal for the Class of All Spanning Trees
• Combinatorial Games

This page was built for publication: Building Spanning Trees Quickly in Maker-Breaker Games