Waiter-Client and Client-Waiter planarity, colorability and minor games

DOI10.1016/j.disc.2015.12.020zbMath1333.05200arXiv1412.1346OpenAlexW1927686689MaRDI QIDQ271623

Dan Hefetz, Wei En Tan, Michael Krivelevich

Publication date: 7 April 2016

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

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

zbMATH Keywords

planaritycolorabilitypositional gamescomplete minors

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (8)

Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ On the odd cycle game and connected rules ⋮ Finding and Using Expanders in Locally Sparse Graphs ⋮ Client-waiter games on complete and random graphs ⋮ Waiter-client triangle-factor game on the edges of the complete graph ⋮ Waiter-client clique-factor game ⋮ Probabilistic intuition holds for a class of small subgraph games ⋮ Waiter-client and client-waiter Hamiltonicity games on random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Picker-chooser fixed graph games
• The picker-chooser diameter game
• Avoider-enforcer: the rules of the game
• Minors in expanding graphs
• Hadwiger's conjecture is true for almost every graph
• Biased positional games on matroids
• Positional games and the second moment method
• On weight function methods in chooser-picker games
• Keeping avoider's graph almost acyclic
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Avoider-Enforcer games
• Odd and even cycles in maker-breaker games
• Positional games
• Asymptotic random graph intuition for the biased connectivity game
• Minors in random regular graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• On the Distribution of the Number of Successes in Independent Trials
• Planarity, Colorability, and Minor Games
• Regularity and Positional Games
• Component behavior near the critical point of the random graph process
• Cycles in a random graph near the critical point
• Biased Positional Games
• On Brooks' Theorem for Sparse Graphs
• Manipulative Waiters with Probabilistic Intuition
• Combinatorial Games
• A Solution of the Shannon Switching Game
• The order of the largest complete minor in a random graph
• On a combinatorial game
• The two possible values of the chromatic number of a random graph
• Biased positional games for which random strategies are nearly optimal

This page was built for publication: Waiter-Client and Client-Waiter planarity, colorability and minor games