Gallai path decomposition beyond odd semi-cliques

Status partial high confidence

Question 1.1 — whether every connected graph that is not an odd semi-clique admits a path decomposition into \lfloor |V(G)|/2 \rfloor paths — remains open in full generality. It has been settled positively for planar graphs (Blanché, Bonamy, Bonichon 2021: every connected planar graph except K_3 and K_5^- decomposes into \lfloor n/2 \rfloor paths) and for 2-degenerate graphs (Anto, Basavaraju 2022: every connected 2-degenerate graph except the triangle decomposes into \lfloor n/2 \rfloor paths). Search results also indicate partial progress for 3-degenerate graphs (2024) but those could not be verified within the call budget.

Cited literature (2)

• partial Gallai's path decomposition in planar graphs (2021)
  Alexandre Blanché, Marthe Bonamy, Nicolas Bonichon · arXiv preprint · arXiv:2110.08870

  Proves the conjecture for planar graphs: every connected planar graph except K_3 and K_5^- (the only two planar odd semi-cliques) can be decomposed into \lfloor n/2 \rfloor paths.

• partial Gallai's Path Decomposition for 2-degenerate Graphs (2022)
  Nevil Anto, Manu Basavaraju · arXiv preprint · arXiv:2211.07159

  Proves the conjecture for 2-degenerate graphs: every connected 2-degenerate graph on n vertices can be decomposed into at most \lfloor n/2 \rfloor paths unless it is a triangle (the only 2-degenerate odd semi-clique).

Reviewer notes. Question 1.1 has been answered positively for planar graphs and 2-degenerate graphs but is open for general connected graphs. A ScienceDirect paper titled 'Gallai's conjecture and the path number of odd semi-cliques' appeared in search results (doi likely 10.1016/j.disc.2025...) but could not be fetched (HTTP 403). Additional partial results for 3-degenerate graphs were indicated in search results but could not be verified within the 5-call budget.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).