On 02.09.2016 at 12:20 in S6, there is the following noon lecture:
Decomposing random d-regular graphs into stars
(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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010