Gallai's Path Decomposition for 2-degenerate Graphs

DOI10.46298/DMTCS.10313arXiv2211.07159MaRDI QIDQ6131797FDOQ6131797

Authors: Manu Basavaraju 

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: Gallai's path decomposition conjecture states that if $G$ is a connected graph on $n$ vertices, then the edges of $G$ can be decomposed into at most $lceilfracn2ceil$ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on $2k+1$ vertices by deleting at most $k-1$ edges. Bonamy and Perrett asked if the edges of every connected graph $G$ on $n$ vertices can be decomposed into at most $lfloorfracn2floor$ paths unless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate if every subgraph of $G$ has a vertex of degree at most $2$. In this paper, we prove that the edges of any connected 2-degenerate graph $G$ on $n$ vertices can be decomposed into at most $lfloorfracn2floor$ paths unless $G$ is a triangle.

Full work available at URL: https://arxiv.org/abs/2211.07159

Recommendations

• Gallai's conjecture for 3-degenerated graphs
• Gallai's path decomposition conjecture for triangle-free planar graphs
• Gallai's path decomposition conjecture for graphs of small maximum degree
• Towards Gallai's path decomposition conjecture
• Gallai's conjecture on path decompositions

zbMATH Keywords

2-degenerate graphspath decompositionseries-parallel graphsouter-planar graphsGallai's path decomposition

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (1)

• Gallai's conjecture for 3-degenerated graphs

This page was built for publication: Gallai's Path Decomposition for 2-degenerate Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131797)