Random 4-regular graphs have 3-star decompositions asymptotically almost surely

2016/10/04 by Delcourt, Michelle, Postle, Luke · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1610.01113

Abstract

In 2006, Barat and Thomassen conjectured in 2006 that the edges of every planar 4-regular 4-edge-connected graph can be decomposed into copies of the star with 3 leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Using the small subgraph conditioning method of Robinson and Wormald, we prove that a random 4-regular graph has an S₃-decomposition asymptotically almost surely, provided the number of vertices is divisible by 3.

Cited by

• Boosted second moment method in random regular graphs

Related

• Decomposing random regular graphs into stars
• The Asymptotic Distributions of 3-star factors in random d-regular graphs
• Star decompositions and independent sets in random regular graphs
• Star decompositions via orientations
• Almost all 5-regular graphs have a 3-flow