High-girth Nash-Williams conjecture for triangle decompositions

Let GG be a graph on G|G| vertices. It is K3K_3-divisible if its number of edges is divisible by 33 and every vertex degree is even. A triangle decomposition with girth at least gg is a partition of the edges into triangles such that no set of fewer than gg vertices spans at least two fewer triangles than vertices.

High-girth Nash-Williams conjecture. For every fixed gg, every sufficiently large K3K_3-divisible graph GG with

δ(G)3G/4\delta(G)\ge 3|G|/4

has a K3K_3-decomposition with girth at least gg.

This combines the minimum-degree triangle-decomposition conjecture with Erdős's local-sparsity requirement. The source presents it as a proposed combination of two unresolved conjectures.

Sources & referencesView supporting material

Primary source

Stefan Glock, Daniela Kühn and Deryk Osthus, “Extremal aspects of graph and hypergraph decomposition problems”, arXiv:2008.00926 (2021).

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.