On minimal arbitrarily partitionable graphs

DOI10.1016/j.ipl.2012.06.010zbMath1248.05152OpenAlexW2057626995MaRDI QIDQ456092

Jakub Przybyło, Olivier Baudon, Mariusz Woźniak

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.06.010

zbMATH Keywords

interconnection networksarbitrary vertex decomposable graphminimal arbitrarily partitionable graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (4)

Dense arbitrarily partitionable graphs ⋮ Unnamed Item ⋮ Partitioning the Cartesian product of a tree and a cycle ⋮ Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs

Cites Work

• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• On the structure of arbitrarily partitionable graphs with given connectivity
• A linear algorithm for bipartition of biconnected graphs
• Decomposing trees with large diameter
• On the shape of decomposable trees
• Decomposable trees: A polynomial algorithm for tripodes
• A degree bound on decomposable trees
• On arbitrarily vertex decomposable trees
• Arbitrarily vertex decomposable caterpillars with four or five leaves
• A homology theory for spanning tress of a graph

This page was built for publication: On minimal arbitrarily partitionable graphs