Options
Creating spanning trees in waiter-client games
Citation Link: https://doi.org/10.15480/882.15877
Publikationstyp
Journal Article
Date Issued
2025-08-22
Sprache
English
Author(s)
Bednarska-Bzdęga, Małgorzata
TORE-DOI
Volume
32
Issue
3
Article Number
P3.35
Citation
The electronic journal of combinatorics 32 (3): P3.35 (2025)
Publisher DOI
Scopus ID
Publisher
Australian National University
For a positive integer n and a tree Tn on n vertices, we consider an unbiased Waiter-Client game WC(n, Tn) played on the complete graph Kn, in which Waiter’s goal is to force Client to build a copy of Tn. We prove that for every constant c < 1/3, if ∆(Tn) ≤ cn and n is sufficiently large, then Waiter has a winning strategy in WC(n, Tn). On the other hand, we show that there exist a positive constant c′ < 1/2 and a family of trees Tn with ∆(Tn) ≤ c′n such that Client has a winning strategy in the WC(n, Tn) game for every n sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.
DDC Class
510: Mathematics
Publication version
publishedVersion
Loading...
Name
12957-PDF file-56334-1-10-20250814.pdf
Size
642.03 KB
Format
Adobe PDF