Towards Gallai's path decomposition conjecture

Autor(es)

Botler, Fabio ^[1] ; Sambinelli, Maycon ^[2]

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

^[1] Univ Fed Rio de Janeiro, Programa Engn Sistemas & Comp, Ave Horacio Macedo 2030, BR-21941972 Rio De Janeiro - Brazil

^[2] Fed Univ ABC, Ctr Matemat Comp & Cognicao, Santo Andre, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF GRAPH THEORY; v. 97, n. 1 NOV 2020.
• 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 conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most left ceiling n / 2 right ceiling . Seminal results toward its verification consider the graph obtained from G by removing its vertices of odd degree, which is called the E-subgraph of G. Lovasz verified Gallai's Conjecture for graphs whose E-subgraphs consist of at most one vertex, and Pyber verified it for graphs whose E-subgraphs are forests. In 2005, Fan verified Gallai's Conjecture for graphs in which each block, that is, each maximal 2-connected subgraph, of their E-subgraph is triangle-free and has maximum degree at most 3. Let G be the family of graphs for which (a) each block has maximum degree at most 3; and (b) each component either has maximum degree at most 3 or has at most one block that contains triangles. In this paper, we generalize Fan's result by verifying Gallai's Conjecture for graphs whose E-subgraphs are subgraphs of graphs in G. This allows the components of the E-subgraphs to contain any number of blocks with triangles as long as they are subgraphs of graphs in G. (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