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

Martin Merker

doi:10.1016/j.endm.2015.06.051

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

Martin Merker

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

805 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 language	English
Journal	Electronic Notes in Discrete Mathematics
Volume	49
Issue number	November 2015
Pages (from-to)	367-370
ISSN	1571-0653
DOIs	https://doi.org/10.1016/j.endm.2015.06.051
Publication status	Published - 2015

Keywords

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

Access to Document

10.1016/j.endm.2015.06.051

3PathSeriesParallelAccepted author manuscript, 139 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{79b505242b1e4070a2d61f929a5a541f,

title = "Decomposing series-parallel graphs into paths of length 3 and triangles",

abstract = "An old conjecture by J{\"u}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.",

keywords = "3-path decomposition, edge-decomposition, planar graph, 2-edge-connected, series-parallel",

author = "Martin Merker",

year = "2015",

doi = "10.1016/j.endm.2015.06.051",

language = "English",

volume = "49",

pages = "367--370",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "November 2015",

}

TY - JOUR

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

AU - Merker, Martin

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - 3-path decomposition

KW - edge-decomposition

KW - planar graph

KW - 2-edge-connected

KW - series-parallel

U2 - 10.1016/j.endm.2015.06.051

DO - 10.1016/j.endm.2015.06.051

M3 - Journal article

SN - 1571-0653

VL - 49

SP - 367

EP - 370

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - November 2015

ER -

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

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this