Decomposing graphs into paths of fixed length

DOI10.1007/s00493-013-2633-7zbMath1299.05270OpenAlexW2067496908WikidataQ56926560 ScholiaQ56926560MaRDI QIDQ2448964

Carsten Thomassen

Publication date: 5 May 2014

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-013-2633-7

zbMATH Keywords

pathspath decompositionedge connectivity

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (15)

A \(\vec{P_3}\)-decomposition of tournaments and bipartite digraphs ⋮ 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 ⋮ On path decompositions of \(2 k\)-regular graphs ⋮ Edge-partitioning 3-edge-connected graphs into paths ⋮ Edge‐decomposing graphs into coprime forests ⋮ Decomposing graphs into paths and trees ⋮ The weak 3-flow conjecture and the weak circular flow conjecture ⋮ Decomposing a graph into bistars ⋮ A proof of the Barát-Thomassen conjecture ⋮ Decomposing highly connected graphs into paths of length five ⋮ Spanning trees and spanning Eulerian subgraphs with small degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weak 3-flow conjecture and the weak circular flow conjecture
• Girth in graphs
• Bounded degree spanning trees (extended abstract)
• Edge-decompositions of highly connected graphs into paths
• Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Decompositions of highly connected graphs into paths of length 3
• Graph decomposition with applications to subdivisions and path systems modulo k
• On partitioning the edges of graphs into connected subgraphs
• On some connectivity properties of Eulerian graphs
• A Reduction Method for Edge-Connectivity in Graphs
• P4-decompositions of regular graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Perfect path double covers of graphs
• Small degree out‐branchings
• Claw‐decompositions and tutte‐orientations
• Minimum partition of a matroid into independent subsets

This page was built for publication: Decomposing graphs into paths of fixed length