Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903569 | European Journal of Combinatorics | 2018 | 15 Pages |
Abstract
Barát 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 S3-decomposition asymptotically almost surely, provided the number of vertices is divisible by 3.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michelle Delcourt, Luke Postle,