Decomposing graphs into long paths

Alexandr Kostochka, Vladimir Tashkinov

Research output: Contribution to journalArticlepeer-review


It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C3, C4, C5, and K4 - e have no such decompositions. We construct an infinite sequence {Fi} i=0 (of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition.

Original languageEnglish (US)
Pages (from-to)239-253
Number of pages15
Issue number3
StatePublished - 2003


  • 2-edge-connected graphs
  • Edge-decompositions of graphs

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Decomposing graphs into long paths'. Together they form a unique fingerprint.

Cite this