Decomposing graphs into paths of fixed length
The paper addresses the following conjecture of Barát and Thomassen: For each tree \(T\) there is a natural number \(k = k(T)\) such that any graph \(G\) that is \(k\)-edge connected with \(| E(T)| \) dividing \(| E(G)| \) can be decomposed into edge disjoint copies of the tree \(T\). This conjecture is verified for any tree \(P\) that is a path of length \(p\) a power of \(2\). The proof involves vertex colorings and multi-edge-colorings of a multi-graph \(G\) with edge-connectivity at least \(\alpha(p, m)\), where each edge has at most \(m\) colors and no vertex sees a color more than once.
- Decomposing highly edge-connected graphs into paths of any given length
- Decompositions of highly connected graphs into paths of any given length
- Decompositions of highly connected graphs into paths of length five
- Decomposing highly connected graphs into paths of length five
- Decomposing graphs into paths and trees
- A Reduction Method for Edge-Connectivity in Graphs
- Bounded degree spanning trees (extended abstract)
- Claw‐decompositions and tutte‐orientations
- Decompositions of highly connected graphs into paths of length 3
- Edge-decompositions of highly connected graphs into paths
- Edge-Disjoint Spanning Trees of Finite Graphs
- Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree
- Girth in graphs
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- Graph decomposition with applications to subdivisions and path systems modulo k
- Graph theory with applications
- Graphs on surfaces
- scientific article; zbMATH DE number 4075098 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 1025912 (Why is no real title available?)
- Minimum partition of a matroid into independent subsets
- On partitioning the edges of graphs into connected subgraphs
- On some connectivity properties of Eulerian graphs
- On the Problem of Decomposing a Graph into n Connected Factors
- P4-decompositions of regular graphs
- Perfect path double covers of graphs
- Small degree out‐branchings
- The weak 3-flow conjecture and the weak circular flow conjecture
- On a theorem of Mader
- Decomposing graphs into paths and trees
- Decomposing highly connected graphs into paths of length five
- A proof of the Barát-Thomassen conjecture
- Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
- Spanning trees and spanning Eulerian subgraphs with small degrees
- A \(\vec{P_3}\)-decomposition of tournaments and bipartite digraphs
- On path decompositions of \(2 k\)-regular graphs
- Edge-partitioning 3-edge-connected graphs into paths
- Path decompositions of regular graphs with prescribed girth
- Decompositions of highly connected graphs into paths of any given length
- On path decompositions of 2k-regular graphs
- Decompositions of highly connected graphs into paths of length five
- Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
- Decomposing highly edge-connected graphs into paths of any given length
- scientific article; zbMATH DE number 5575592 (Why is no real title available?)
- scientific article; zbMATH DE number 91047 (Why is no real title available?)
- The weak 3-flow conjecture and the weak circular flow conjecture
- Decomposing a graph into bistars
- scientific article; zbMATH DE number 3895103 (Why is no real title available?)
- Edge‐decomposing graphs into coprime forests
This page was built for publication: Decomposing graphs into paths of fixed length
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448964)
