The simultaneous clique-maximisation conjecture for graphs on surfaces
The simultaneous clique-maximisation conjecture for graphs on surfaces
Let be an -vertex graph embeddable in a surface . Let denote its total number of complete subgraphs, let be the maximum of over all such graphs, and let be the maximum number of copies of in an -vertex graph embeddable in .
Simultaneous clique-maximisation conjecture. If , then for every ,
This is the equality-case counterpart of the clique-count decomposition conjecture: every graph attaining the maximum total clique count should also attain each individual clique-count maximum. It has been verified for the surfaces listed in the paper, while the assertion for arbitrary surfaces remains open.
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
Tony Huynh, Gwenaël Joret and David R. Wood, “Subgraph densities in a surface”, arXiv:2003.13777 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.