EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On a Clique‐Building Game of Erdős

Alexandru Malekshahian, Sam Spiro

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →