Leírás
The caterpillar packing conjecture is the following: Let $M$ be a
$k\times n$ matrix of positive integers such that each row sum is
$2n-2$ and each column contains at most one $1$. Then there exists a
simple, edge colored, vertex labelled graph on $n$ vertices such that
its $i^{th}$ colored subgraph is a caterpillar, and for each $j$, the
degree of vertex $v_j$ in that subgraph is $m_{i,j}$. With other
words: there exist edge disjoint caterpillar realizations of the rows
on $M$. Recall that a caterpillar is a tree in which the non-leaves
form a path.
We will prove the conjecture for $k<5$. We have a computer-aided proof
that the conjecture is true for $k=5$. Above that we have the
following two theorems:
Theorem 1: If the caterpillar packing conjecture is true for each n <
4k, then it is true.
Theorem 2: Let $M$ be a $k\times n$ matrix of positive integers such
that each row sum is $2n+2$ and each column contains at most one $1$.
Furthermore, let $n \ge 36k$. Then there exist edge disjoint
caterpillar realizations of the rows on $M$.