Arbitrarily partitionable graphs

The studies of arbitrarily partitionable or arbitrary decomposable graphs (more strictly speaking - trees) were independently initiated by two groups of authors corresponding to the first two papers on this subject:

  • D.Barth, O.Baudon and J.Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002), 205-216.
  • M. Horňák, M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Mathematica 23 (2003), 49-62.

The motivation for the French group (from LRI in Orsay) was a division problem of a large computer network and allocating its parts to independent users. The Slovak-Polish group (from UJPS in Kosice and AGH) intended to transfer the problem of arbitrary partitions of edge sets into the vertex setting.

A survey of the results up to 2008 is included, e.g., in the overview presentation [delivered as a plenary lecture at the Second Polish Combinatorial Conference (2nd Polish Combinatorial Conference, 2PCC) in Będlewo in 2008.]