On a conjecture of Graham and Häggkvist with the polynomial method

A conjecture of Graham and Häggkvist states that every tree with mm edges decomposes every 2m2m-regular graph and every bipartite mm-regular graph. Let TT be a tree with a prime number pp of edges. We show that if the growth ratio of TT at some vertex v0v0 satisfies ρ(T,v0)≥ϕ1/2ρ(T,v0)≥ϕ1/2, where ϕ=1+52 is the golden ratio, then TT decomposes K2p,2pK2p,2p. We also prove that if TT has at least p/3p/3 leaves then it decomposes K2p,2pK2p,2p. This improves previous results by Häggkvist and by Lladó and López. The results follow from an application of Alon’s Combinatorial Nullstellensatz to obtain bigraceful labelings.