The concise tree-counting conjecture for planar graphs

Let G=(V,E)G=(V,E) be a simple planar graph, and let tr(G)tr(G) be the number of trees in GG of all sizes. Planar tree-counting conjecture. The function trtr is concise: every positive integer should be realized by a planar graph whose size is bounded by a fixed polynomial in the logarithm of that integer. The function is already almost complete because an empty graph on nn vertices has nn trees, and its computation is #P\#\mathrm P-complete, but conciseness remains open.

Sources & referencesView supporting material

Primary source

Swee Hong Chan and Igor Pak, “Computational complexity of counting coincidences”, arXiv:2308.10214 (2024).

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.