GALLAI'S PATH DECOMPOSITION CONJECTURE FOR GRAPHS WITH MAXIMUM E-DEGREE AT MOST 3

Author(s)

Botler, F. ^[1] ; Sambinelli, M. ^[2]

Affiliation

^[1] Univ Fed Rio de Janeiro, Programa Engn Sistemas & Comp, Rio De Janeiro - Brazil

^[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil

• Document type: Journal article
• Source: ACTA MATHEMATICA UNIVERSITATIS COMENIANAE; v. 88, n. 3, p. 501-505, 2019.
• Web of Science Citations: 0

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 left perpendicular(n+1)/2right perpendicular. 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. Lovasz (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. (AU)

• FAPESP's process: 17/23623-4 - Partition problems in graphs and digraphs
• Grantee: Maycon Sambinelli
• Support Opportunities: Scholarships in Brazil - Post-Doctoral