On a Häggkvist's Conjecture with the Polynomial Method

A conjecture of Häggkvist states that every tree with m edges decomposes every 2m–regular graph. Let T be a tree with a prime number p of edges. We show that if the growth ratio of T at some vertex v0 satisfies ρ(T,v0)≥ϕ1/2, where is the golden ratio, then T decomposes K2p,2p. We also prove that if T has at least p/3 leaves then it decomposes K2p,2p. The results follow from an application of Alon's Combinatorial Nullstellensatz to obtain bigraceful labelings.