Mohr et al.'s low-sum spanning forest conjecture

Let KnK_n be a complete graph of order nn, and let c:E(Kn){1,1}c:E(K_n)\to \{-1,1\} be a zero-sum labeling satisfying

c(E(Kn))=eE(Kn)c(e)=0.c(E(K_n))=\sum_{e\in E(K_n)}c(e)=0.

Let FF be a spanning forest of KnK_n with maximum degree Δ\Delta. Mohr et al.'s conjecture. There is an isomorphic copy FF' of FF in KnK_n such that

c(E(F))12Δ12.|c(E(F'))|\leq \frac{1}{2}\Delta-\frac{1}{2}.

This would improve the previously known bound c(E(F))Δ+1|c(E(F'))|\leq \Delta+1 and concerns the existence of low-sum copies of spanning forests in zero-sum edge-labeled complete graphs. The supplied source does not establish whether the conjecture is resolved.

Sources & referencesView supporting material

Primary source

Johannes Pardey and Dieter Rautenbach, “Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation”, arXiv:2102.10940 (2021).

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.