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

From papers

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 FF' 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.

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

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

Solutions 0

No solutions have been posted yet.