Henning's Sweller-start competition-independence conjecture for trees

From papers

Let TT be a tree of order nn. The competition-independence number Is(T)I_s(T), namely the length of the competition-independence game when Sweller moves first and both players play optimally, satisfies

Is(T)37n.I_s(T) \geq \frac{3}{7}n.

Henning's conjecture. For every tree TT of order nn, Is(T)37nI_s(T) \geq \frac{3}{7}n. The paper disproves this conjecture by exhibiting arbitrarily large trees for which the Sweller-start game lasts at most (5n+26)/12(5n+26)/12 moves, while proving the general lower bound Is(T)(5n+3)/13I_s(T)\geq(5n+3)/13.

Progress summary

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

Sources & referencesView supporting material

Primary source

Jan Petr and Julien Portier, “Bounds for the Competition-Independence game on trees”, arXiv:2303.09993 (2023).

Solutions 0

No solutions have been posted yet.