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.)

Gallai's path decomposition conjecture for graphs with treewidth at most 3

Full text
Author(s):
Botler, Fabio [1] ; Sambinelli, Maycon [2] ; Coelho, Rafael S. [3] ; Lee, Orlando [4]
Total Authors: 4
Affiliation:
[1] Univ Fed Rio de Janeiro, Programa Engn Sistemas & Comp, POB 68511, BR-21941972 Rio De Janeiro - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[3] Univ Fed Rio Grande do Sul, Inst Informat, Porto Alegre, RS - Brazil
[4] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Total Affiliations: 4
Document type: Journal article
Source: JOURNAL OF GRAPH THEORY; AUG 2019.
Web of Science Citations: 0
Abstract

A path decomposition of a graph G is a set of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph with n vertices admits a path decomposition of size at most L(n+1)/2<SIC> RIGHT FLOOR. Gallai's conjecture was verified for many classes of graphs. In particular, Lovasz (1968) verified this conjecture for graphs with at most one vertex of even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified Gallai's conjecture for graphs with maximum degree at most 5. In this paper, we verify Gallai's conjecture for graphs with treewidth at most 3. Moreover, we show that the only graphs with treewidth at most 3 that do not admit a path decomposition of size at most Ln/2<SIC> RIGHT FLOOR are isomorphic to K3 or K5-, the graph obtained from K5 by removing an edge. (AU)

FAPESP's process: 17/23623-4 - Partition problems in graphs and digraphs
Grantee:Maycon Sambinelli
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
Grantee:Carlos Eduardo Ferreira
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support Opportunities: Research Projects - Thematic Grants