Towards Gallai's path decomposition conjecture

Author(s)

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

Affiliation

^[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

• Document type: Journal article
• Source: JOURNAL OF GRAPH THEORY; v. 97, n. 1 NOV 2020.
• 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 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)

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