Liu–Montgomery's crux conjecture for clique subdivisions
Liu–Montgomery's crux conjecture for clique subdivisions
Let be a graph and let . For a subgraph , write for its average degree, and let be the minimum order of a subgraph with . A subdivision of a clique is obtained by replacing each edge of the clique by internally vertex-disjoint paths.
Liu–Montgomery's crux conjecture. There exists some constant such that every graph contains a subdivision of a clique with at least
vertices.
The conjecture formalizes the idea that graphs without a small subgraph almost as dense as the whole graph should contain a large clique subdivision. The parameter is the crux, measuring the order of the smallest dense patch; the source states that Liu and Montgomery raised this conjecture with , but gives no resolution here.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Donglei Yang and Fan Yang, “Embedding clique subdivisions via crux”, arXiv:2405.15409 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.