Bounded path covering with forests number for non-crossing shortest paths

From papers

Let GG be a plane graph, and let PP be a set of non-crossing single-touch shortest paths in GG. The path covering with forests number of PP, denoted by PCFN(P)\operatorname{PCFN}(P), is the minimum number of forests needed to cover the paths in PP. Bounded path covering conjecture. There exists N\ell\in\mathbb{N} such that

PCFN(P)\operatorname{PCFN}(P)\leq\ell

for every set PP of non-crossing single-touch shortest paths in a plane graph. This asks whether the path covering with forests number is bounded by a universal constant when the paths' extremal vertices are not required to lie on the same face; the paper presents this as a generalization for future work and gives a related remark without proof.

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

Lorenzo Balzotti, “Non-Crossing Shortest Paths are Covered with Exactly Four Forests”, arXiv:2210.13036 (2022).

Solutions 0

No solutions have been posted yet.