Online packing of the three largest trees
Source: arxiv.org/abs/2611.04674
For every $n\ge4$, arbitrary trees of orders $n,n-1,n-2$ can be packed into $K_n$ online, in decreasing order of size: each tree must be embedded before the next is revealed, and earlier embeddings cannot be changed. This strengthens the classical three-tree packing theorem of Hobbs, Bourgeois and Kasiraj (1987). In particular, the second tree is embedded without knowing the third, and the resulting pair of copies can be extended to accommodate every possible third tree. Our strategy is to embed the first two trees so that their union is $2$-degenerate. We prove that the complement of every…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.04674
curl -X POST /api/v1/records/arxiv/2611.04674/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04674/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'