The 1/10 upper-bound conjecture for triangle expansions

Let GG be a bridgeless cubic graph. For UV(G)U\subseteq V(G), let GUG_U be obtained by expanding each vertex of UU into a triangle, and let T(G)T(G) be the minimum size of a set UU for which the edge-set of GUG_U can be covered with four perfect matchings. The 1/101/10 upper-bound conjecture. Every bridgeless cubic graph GG satisfies

T(G)V(G)10.T(G)\leq \frac{|V(G)|}{10}.

The paper proves the weaker bound T(G)25V(G)T(G)\leq \frac{2}{5}|V(G)| assuming the 5-cycle double cover conjecture. The proposed bound remains open.

Sources & referencesView supporting material

Primary source

Giuseppe Mazzuoccolo and Vahan Mkrtchyan, “Expanding vertices to triangles in cubic graphs”, arXiv:2504.19201 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.