Waiter-client and client-waiter colourability and \(k\)-SAT games

zbMath1366.05072arXiv1607.02258MaRDI QIDQ2363109

Wei En Tan

Publication date: 13 July 2017

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

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

zbMATH Keywords

colouringpositional games\(k\)-SAT

Mathematics Subject Classification ID

2-person games (91A05) 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

Waiter-client triangle-factor game on the edges of the complete graph, Waiter-client clique-factor game

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Picker-chooser fixed graph games
• The picker-chooser diameter game
• The asymptotic \(k\)-SAT threshold
• On chooser-picker positional games
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Positional games and the second moment method
• On weight function methods in chooser-picker games
• On the chromatic number of a random hypergraph
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Positional games
• The Power of Choice for Random Satisfiability
• Delaying satisfiability for random 2SAT
• Proof of the Satisfiability Conjecture for Large k
• Random k -SAT and the power of two choices
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The Lovász Local Lemma and Satisfiability
• The Game of Hex and the Brouwer Fixed-Point Theorem
• On the 2-colorability of random hypergraphs
• Two‐coloring random hypergraphs
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Hypergraph coloring up to condensation
• Manipulative Waiters with Probabilistic Intuition
• Combinatorial Games
• The condensation transition in random hypergraph 2-coloring
• The two possible values of the chromatic number of a random graph