---

Claim. G. Fan, Path decompositions and Gallai's conjecture, J. Combin. Theory Ser. B 93 (2005), 117--125, published online on 11 November 2004 (the claim's date). Its Main theorem (p. 124): a graph on $n$ vertices, not necessarily connected, whose vertices of even degree induce an $\alpha$-graph decomposes into $\lfloor n/2\rfloor$ paths. An $\alpha$-graph is one built from the empty graph by adding isolated vertices and vertices joined to the independent sets of $\alpha$-pairs (Definitions 2.1--2.2, pp. 118--119); every $\alpha$-graph is triangle-free, and forests are $\alpha$-graphs. Its Corollary (p. 125): the same holds when each block of the even-degree subgraph is a triangle-free graph of maximum degree at most $3$, since such graphs are $\alpha$-graphs (Proposition 2.6). The paper shows (p. 118) that the triangle-free condition cannot be dropped. The theorems are recorded on the Main theorem page and the Corollary page of the source card.

Covers. The statement of Problem 583 for connected graphs whose even-degree subgraph is an $\alpha$-graph, including those in which each block of the even-degree subgraph is triangle-free with maximum degree at most $3$, with $\lfloor n/2\rfloor$ paths.

Depends on. Nothing in this wiki.

Acceptance. Refereed: the paper is a publication in the Journal of Combinatorial Theory, Series B. The site does not cite the paper.