Decomposing series-parallel graphs into paths of length 3 and triangles

Martin Merker

Research output: Contribution to journalJournal articleResearchpeer-review

578 Downloads (Orbit)

Abstract

An old conjecture by Jünger, Reinelt and Pulleyblank states that every 2-edge-connected planar graph can be decomposed into paths of length 3 and triangles, provided its size is divisible by 3. We prove the conjecture for a class of planar graphs including all 2-edge-connected series-parallel graphs. We also present a 2-edge-connected non-planar graph that can be embedded on the torus and admits no decomposition into paths of length 3 and triangles.
Original languageEnglish
JournalElectronic Notes in Discrete Mathematics
Volume49
Issue numberNovember 2015
Pages (from-to)367-370
ISSN1571-0653
DOIs
Publication statusPublished - 2015

Keywords

  • 3-path decomposition
  • edge-decomposition
  • planar graph
  • 2-edge-connected
  • series-parallel

Fingerprint

Dive into the research topics of 'Decomposing series-parallel graphs into paths of length 3 and triangles'. Together they form a unique fingerprint.

Cite this