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

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)

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)