Title: On Gallai's and Hajós' Conjectures for graphs with treewidth at most 3,
Abstract: A path (resp. cycle) decomposition of a graph $G$ is a set of edge-disjoint
paths (resp. cycles) of $G$ that covers the edge set of $G$. Gallai (1966)
conjectured that every graph on $n$ vertices admits a path decomposition of
size at most $\lfloor (n+1)/2\rfloor$, and Hajós (1968) conjectured that
every Eulerian graph on $n$ vertices admits a cycle decomposition of size at
most $\lfloor (n-1)/2\rfloor$. Gallai's Conjecture was verified for many
classes of graphs. In particular, Lovász (1968) verified this conjecture for
graphs with at most one vertex of even degree, and Pyber (1996) verified it for
graphs in which every cycle contains a vertex of odd degree. Hajós'
Conjecture, on the other hand, was verified only for graphs with maximum degree
$4$ and for planar graphs. In this paper, we verify Gallai's and Hajós'
Conjectures for graphs with treewidth at most $3$. Moreover, we show that the
only graphs with treewidth at most $3$ that do not admit a path decomposition
of size at most $\lfloor n/2\rfloor$ are isomorphic to $K_3$ or $K_5-e$.
Finally, we use the technique developed in this paper to present new proofs for
Gallai's and Hajós' Conjectures for graphs with maximum degree at most $4$,
and for planar graphs with girth at least $6$.