On a Clique‐Building Game of Erdős
Journal of Graph Theory · 2026-10 · 113 (2) · 208-221
DOI: 10.1002/jgt.70061 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 14.05.2026. Verfasst von Alexandru Malekshahian und 1 weiteren Autor:innen. Die Arbeit nennt 6 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- National Science Foundation
Zitieren
APA
Malekshahian, A., & Spiro, S. (2026). On a Clique‐Building Game of Erdős. Journal of Graph Theory, 113(2), 208-221. https://doi.org/10.1002/jgt.70061
Vancouver
Malekshahian A, Spiro S. On a Clique‐Building Game of Erdős. Journal of Graph Theory. 2026;113(2):208-221. doi:10.1002/jgt.70061
BibTeX
@article{Malekshahian2026,
author = {Malekshahian, Alexandru and Spiro, Sam},
title = {On a Clique‐Building Game of Erdős},
journal = {Journal of Graph Theory},
year = {2026},
volume = {113},
number = {2},
pages = {208--221},
doi = {10.1002/jgt.70061}
}
EUVIMED