%A Botler, Fábio
%A Sambinelli, Maycon
%D 2019
%T Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3
%K
%X 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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1195
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 501-505%V 88
%N 3
%@ 0862-9544
%8 2019-07-26