Edge-partitioning 3-edge-connected graphs into paths

DOI10.1016/J.JCTB.2022.05.001MaRDI QIDQ2673486zbMATH OpenOpenAlexFDO

Authors Tereza Klimošová, Stéphan Thomassé

Publication date 10 June 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Barát-Thomassen conjecturedecomposition into pathsedge-decomposition

Mathematics Subject Classification ID

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

Abstract: We show that for every l, there exists d_l such that every 3-edge-connected graph with minimum degree d_l can be edge-partitioned into paths of length l (provided that its number of edges is divisible by l). This improves a result asserting that 24-edge-connectivity and high minimum degree provides such a partition. This is best possible as 3-edge-connectivity cannot be replaced by 2-edge connectivity.

Review text

For two given graphs \(G\) and \(H\), we say that \(G\) is \(H\)-decomposable if there exists a partition \(\{E_i\}_{i\in [k]}\) of \(E(G)\) such that each \(E_i\) forms an isomorphic copy of \(H\). We then call \(\{E_i\}_{i\in [k]}\) an \(H\)-decomposition of \(G\). Many researchers presented some conditions for the existence of \(H\)-decompositions of graphs, such as tree-decomposition, cycle-decomposition, path-decomposition, clique- decomposition, and triangle-decomposition. In this paper, the authors show that for every \(\ell\), there exists \(d_{\ell}\) such that every 3-edge-connected graph with minimum degree \(d_{\ell}\) can be edge-partitioned into paths of length \(\ell\) (provided that its number of edges is divisible by \(\ell\)), which improves a result asserting that 24-edge-connectivity and high minimum degree provides such a partition. Furthermore, the authors show that 3-edge-connectivity in the main result is the best possible, that is, 3-edge-connectivity in the main result cannot be replaced by 2-edge connectivity.

Recommendations

• Decompositions of highly connected graphs into paths of length 3
• On partitioning the edges of graphs into connected subgraphs
• Edge-decompositions of highly connected graphs into paths
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Decomposing graphs into long paths

Cites work

• A constructive proof of the general Lovász local lemma
• A generalization of Kónig's theorem
• A proof of the Barát-Thomassen conjecture
• A Reduction Method for Edge-Connectivity in Graphs
• Claw‐decompositions and tutte‐orientations
• Decomposing graphs into paths of fixed length
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Edge‐decomposing graphs into coprime forests
• scientific article; zbMATH DE number 446493 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• The weak 3-flow conjecture and the weak circular flow conjecture

Cited in

(8)

• Edge-decompositions of highly connected graphs into paths
• Efficient algorithms for path partitions
• Decomposing graphs into long paths
• Decompositions of highly connected graphs into paths of length 3
• scientific article; zbMATH DE number 554067 (Why is no real title available?)
• Length 3 edge-disjoint paths is NP-hard
• Partitions of the edge set of a graph into internally disjoint paths
• Hypertree shrinking avoiding low degree vertices

This page was built for publication: Edge-partitioning 3-edge-connected graphs into paths

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