Gallai’s conjecture on certain families of bipartite graphs

Gallai’s conjecture asks whether every connected graph can have its edges partitioned into at most half its vertices’ worth of paths, rounded up. The general conjecture remains open.

Known results and recent publication (date not stated)

• Complete bipartite graphs satisfy the conjectured bound.
• Connected $2$-degenerate graphs satisfy it, with a stronger bound except for triangles.
• The order-one Levi graphs $L_1(m,k)$ satisfy the stronger bound $p(G)\le\lfloor n/2\rfloor$ for $m\ge 2$ and $2\le k\le m$; for $k=2$, equality is claimed.
• Sahu and Padinhatteeri’s article, “Gallai’s Conjecture on Certain Families of Bipartite Graphs,” appeared in La Matematica; its accessible publication record gives no exact online date or theorem statement, while the associated preprint reports the $L_1(m,k)$ result.

Community submission (unverified)

Posted September 9, 2026. A submitted argument studies the point–triple Levi graphs $L_n(m,3)$, claims exact path counts in some congruence classes of $m$, and gives a ten-path decomposition for $m=6$. It identifies the remaining cases with a uniform triple-terminal routing problem; none of these claims has independent verification.

Current status (as of September 2026): The conjecture is claimed for several graph classes, including $L_1(m,k)$, but remains open in general; the point–triple claims are unverified.