Decompositions into two linear forests of bounded lengths

DOI10.1016/J.DISC.2024.113962MaRDI QIDQ6424564zbMATH OpenOpenAlexFDO

Authors Rutger Campbell, Florian Hoersch, Benjamin Moore

Publication date 27 January 2023

Full work available at URL https://doi.org/10.1016/j.disc.2024.113962

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: For some $kinmathbb{Z}_{geq0}cupinfty$, we call a linear forest $k$-bounded if each of its components has at most $k$ edges. We will say a $(k,ell)$-bounded linear forest decomposition of a graph $G$ is a partition of $E(G)$ into the edge sets of two linear forests $F_k,F_{e}ll$ where $F_k$ is $k$-bounded and $F_{e}ll$ is $ell$-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both $k$ and $ell$ are at least $2$, NP-complete if $kgeq9$ and $ell=1$, and is in P for $(k,ell)=(2,1)$. Before this, the only known NP-complete cases were the $(2,2)$ and $(3,3)$ cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than $3$-edge-colouring such graphs.

Recommendations

• Complexity results on the decomposition of a digraph into directed linear forests and out-stars
• Decomposing a graph into forests
• Decomposing a planar graph with girth 9 into a forest and a matching
• Complexité de l'arboricité linéaire d'un graphe II
• Edge decompositions into two kinds of graphs

Cited in

(2)

• Complexity results on the decomposition of a digraph into directed linear forests and out-stars
• The complexity of decomposing a graph into a matching and a bounded linear forest

This page was built for publication: Decompositions into two linear forests of bounded lengths

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