The odd-bridge conjecture for 2-linear trees

Let TT be a 22-linear tree, and let its bridge be the distinguished path joining its two linear components. Write Max(T)\operatorname{Max}(T) for the set of maximum arrangements of TT, and MaxBip(T)\operatorname{MaxBip}(T) for the set of maximal bipartite arrangements of TT.

Odd-bridge conjecture. If the bridge of TT has odd length, then no maximal non-bipartite arrangement is a maximum arrangement; equivalently,

Max(T)=MaxBip(T).\operatorname{Max}(T)=\operatorname{MaxBip}(T).

The conjecture is motivated by exhaustive data showing that odd-bridge 22-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

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.