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

Main Article Content

Fábio Botler Maycon Sambinelli

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.

Article Details

How to Cite
Botler, F., & Sambinelli, M. (2019). Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3. Acta Mathematica Universitatis Comenianae, 88(3), 501-505. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1195/687
Section
EUROCOMB 2019