Graph Theory Seminar - Luke Postle

Title: Claw decompositions of random 4-regular graphs

Abstract:  In 2005, Barat and Thomassen conjectured that the edges of every planar 4-regular 4-edge-connected graph can be decomposed into claws; shortly afterwards, Lai constructed a counterexample to this conjecture.  Using the small subgraph conditioning method of Wormald, we show that a.a.s. a random 4-regular graph has such a claw decomposition. Joint work with Michelle Delcourt.