Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903505 | Electronic Notes in Discrete Mathematics | 2017 | 6 Pages |
Abstract
Gallai conjectured (1966) that the edge-set of a simple graph G with n vertices can be covered by at most (n+1)/2 edge-disjoint paths. Lovász [Lovász, L., On covering of graphs, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968 pp. 231-236.] verified this conjecture for graphs with at most one vertex of even degree, and Pyber [Pyber, L., Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B 66 (1996), pp. 152-159.] verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified this Conjecture for graphs with maximum degree at most 5. In this paper, we verify the Conjecture for graphs with treewidth at most 3.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Fábio Botler, Maycon Sambinelli,