Waiter–Client tree-universality conjecture

Let KnK_n be the complete graph on nn vertices. A graph is tree-universal at degree bound DD if it contains a copy of every tree TT with nn vertices and maximum degree Δ(T)D\Delta(T)\leq D. Waiter–Client tree-universality conjecture. There exists a constant c>0c>0 such that, for every sufficiently large integer nn, in the (1:1)(1:1) Waiter–Client game on KnK_n, Waiter has a strategy forcing Client to claim a graph that is tree-universal at degree bound cncn. The source says that the established degree order in the Waiter–Client theorem should be improvable, but gives no resolution of this conjecture.

Sources & referencesView supporting material

Primary source

Grzegorz Adamski, Sylwia Antoniuk, Małgorzata Bednarska-Bzdęga, Dennis Clemens, Fabian Hamann and Yannick Mogge, “Tree universality in positional games”, arXiv:2312.00503 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.