The clique-count conjecture for complete minor-free graphs

Let cliques(n,t)\textup{cliques}(n,t) denote the maximum number of cliques in an nn-vertex graph with no KtK_t-minor. Clique-count conjecture.

cliques(n,t)=2t2(nt+3)if and only ift49.\textup{cliques}(n,t)=2^{t-2}(n-t+3)\quad\text{if and only if}\quad t\leq 49.

The bound is motivated by complete multipartite graphs, and computer search verifies it for t49t\leq 49; examples based on Kc×2K_{c\times 2} disprove the bound for sufficiently large tt, including every t62t\geq 62.

Sources & referencesView supporting material

Primary source

David R. Wood, “Cliques in Graphs Excluding a Complete Graph Minor”, arXiv:1511.04655 (2016).

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.