Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Towards Gallai's path decomposition conjecture

Full text
Author(s):
Botler, Fabio [1] ; Sambinelli, Maycon [2]
Total Authors: 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
Total Affiliations: 2
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