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

About 3 years old · traced to

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.

References

Primary source

Jan Petr and Julien Portier, “Bounds for the Competition-Independence game on trees”, arXiv:2303.09993 (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.