On a Clique‐Building Game of Erdős
Abstract
ABSTRACT The following game was introduced in a list of open problems from 1983 attributed to Erdős: two players take turns claiming edges of a until all edges are exhausted. Player 1 wins the game if the largest clique that they claim at the end is strictly larger than the largest clique of their opponent; otherwise, Player 2 wins the game. Erdős conjectured that Player 2 always wins this game for . We make the first known progress on this problem, proving that this holds for at least 3/4 of all such . We also address a biased version of this game, as well as the corresponding degree‐building game, both of which were originally proposed by Erdős as well.
Fields of Study & Subjects
Artificial Intelligence in Games
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- Journal of Graph Theory
- Volume
- 113
- Issue
- 2
- Pages
- 208–221
- Publication date
- 14 May 2026
- Language
- EN