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

Autor(es)

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

Afiliação do(s) autor(es)

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

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

• Tipo de documento: Artigo Científico
• Fonte: ACTA MATHEMATICA UNIVERSITATIS COMENIANAE; v. 88, n. 3, p. 501-505, 2019.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 17/23623-4 - Problemas de partição em grafos e dígrafos
• Beneficiário: Maycon Sambinelli
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado