Mohr–Pardey–Rautenbach conjecture on almost colour-balanced spanning forests

About 2 years old · traced to

Let KnK_n be the complete graph on nn vertices, and let c:E(Kn)→{−1,+1}c:E(K_n)\rightarrow\{-1,+1\} be a balanced colouring, meaning that c(Kn)=0c(K_n)=0. Let FF be an nn-vertex forest with maximum degree Δ\Delta.

Mohr–Pardey–Rautenbach conjecture. There exists a copy F′F' of FF in KnK_n such that

∣c(F′)∣≤12(Δ−1).\left|c(F')\right|\leq \tfrac{1}{2}(\Delta-1).

This conjecture asks how close to colour-balanced a spanning copy of an arbitrary forest can be in a balanced two-colouring of the complete graph. It generalises known results for perfect matchings, factors of paths, and spanning paths; its general case is presented as open in the source.

References

Primary source

Lawrence Hollom, Adva Mond and Julien Portier, “Almost colour-balanced spanning forests in complete graphs”, arXiv:2410.06148 (2024).

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.