Gallai's path decomposition conjecture for triangle-free planar graphs

Autor(es)

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

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

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

^[2] Univ Valparaiso, CIMFAV, Fac Ingn, Valparaiso - Chile

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

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 342, n. 5, p. 1403-1414, MAY 2019.
• Citações Web of Science: 3

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. Gallai's Conjecture has been verified for many classes of graphs. In particular, Lovasz (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai's Conjecture for graphs with maximum degree at most 5, and Botler et al. (2017) verified it for graphs with treewidth at most 3. In this paper, we verify Gallai's Conjecture for triangle-free planar graphs. (C) 2019 Elsevier B.V. All rights reserved. (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