Claims

../

1968_01_01_lovasz: Lovász proves that a graph with at most one vertex of even degree decomposes into at most floor(n/2) paths, as later papers quote it; a proceedings paper.

1996_01_01_pyber: Pyber proves that a graph each of whose cycles contains a vertex of odd degree decomposes into at most floor(n/2) paths; refereed in J. Combin. Theory Ser. B.

2004_11_11_fan: Fan proves floor(n/2) paths when the subgraph induced by the even-degree vertices is an alpha-graph, which includes the forests and the triangle-free blocks of maximum degree 3; refereed in J. Combin. Theory Ser. B.

2016_09_20_bonamy_perrett: Bonamy and Perrett prove Gallai's conjecture for connected graphs of maximum degree at most 5; refereed in Discrete Mathematics.

2021_08_24_blanche_bonamy_bonichon: Blanché, Bonamy and Bonichon claim that every connected planar graph other than K_3 and K_5 minus an edge decomposes into floor(n/2) paths; an extended abstract and a 95-page preprint, with no journal version.

2022_11_14_anto_basavaraju: Anto and Basavaraju prove that every connected 2-degenerate graph other than the triangle decomposes into at most floor(n/2) paths; refereed in DMTCS.

2025_08_18_chu_fan_zhou: Chu, Fan and Zhou prove floor(n/2)+1 paths when the even-degree vertices induce K_m with m at most 15, which is Gallai's bound for odd n; refereed in Discrete Mathematics.

2026_08_31_sallerk: A forum comment of August 2026 reports an exhaustive computer check that every connected graph on at most eleven vertices splits into at most n over two rounded up edge-disjoint paths; reproduced in the thread, unreviewed.

2026_09_17_herong: A forum comment of September 2026 reports an independent decider and exhaustive sweeps showing that every connected graph on at most eleven vertices meets Gallai's bound; unreviewed.

---