Waiter–Client tree-universality conjecture

About 3 years old · traced to

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.

References

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.