Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3

Abstract

A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most (n+1)/2. Seminal results toward its verification consider the graph obtained from G by removing its vertices with odd degree, which is called the E-subgraph of G. Lovász (1968) verified Gallai's Conjecture for graphs whose E-subgraphs consist of at most one vertex, and Pyber (1996) verified it for graphs whose E-subgraphs are forests. In 2005, Fan verified Gallai's Conjecture for graphs whose E-subgraphs are triangle-free and contain only blocks with maximum degree at most 3. Since then, no result was obtained regarding E-subgraphs. In this paper, we verify Gallai's Conjecture for graphs whose E-subgraphs have maximum degree at most 3.