On a Clique‐Building Game of Erdős

Journal article

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 K n ${K}_{n}$ 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 n ≥ 3 $n\ge 3$ . We make the first known progress on this problem, proving that this holds for at least 3/4 of all such n $n$ . 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.

Authors: Malekshahian, A; Spiro, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Journal of Graph Theory
• Article number: jgt.70061
• Publication date: 2026-05-14
• Acceptance date: 2026-04-28
• DOI: 10.1002/jgt.70061
• EISSN: 1097-0118
• ISSN: 0364-9024
• Language: English