The odd-bridge conjecture for 2-linear trees
The odd-bridge conjecture for 2-linear trees
Let be a -linear tree, and let its bridge be the distinguished path joining its two linear components. Write for the set of maximum arrangements of , and for the set of maximal bipartite arrangements of .
Odd-bridge conjecture. If the bridge of has odd length, then no maximal non-bipartite arrangement is a maximum arrangement; equivalently,
The conjecture is motivated by exhaustive data showing that odd-bridge -linear trees of the tested orders are maximizable only by bipartite arrangements. A proof for all such trees is not supplied.
Sources & referencesView supporting material
Primary source
Lluís Alemany-Puig, Juan Luis Esteban and Ramon Ferrer-i-Cancho, “Maximum Linear Arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs”, arXiv:2312.04487 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.