Decomposing random d-regular graphs into stars

Bernard Lidicky

Abstract

(joint work with Delcourt and Postle)

In 2006 Barat and Thomassen conjectured that every planar 4-regular 4-edge-connected graph has an edge decomposition into claws; shortly after, Lai constructed a counterexample. Recently, Delcourt and Postle showed that a random 4-regular graph has an edge decomposition into claws a.a.s.. We generalize the result to decomposition of d-regular graphs into stars for some other values of d. We use the small subgraph conditioning method of Robinson and Wormald.