Gallai's conjecture for graphs with treewidth 3
| Autor: | Fábio Botler, Maycon Sambinelli |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Clique-sum Applied Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences 1-planar graph Treewidth Combinatorics Indifference graph Pathwidth 010201 computation theory & mathematics Chordal graph Partial k-tree Discrete Mathematics and Combinatorics 0101 mathematics Lonely runner conjecture Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 62:147-152 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2017.10.026 |
| Popis: | 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. Lovasz [Lovasz, 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect