Characterisation of polynomial-growth graphs by products of trees
For a graph , write for its growth function, and let denote the strong product of graphs and . Let be the complete graph on vertices. A graph has polynomial growth with parameters and when , and each below is a tree with growth bounded linearly in .
Polynomial-growth product-structure conjecture. There exist functions and such that for any and , every graph with growth is isomorphic to a subgraph of
where each is a tree of growth .
This is presented as a more general rough characterisation of graphs of polynomial growth, extending the preceding linear-growth conjecture. Its status is unresolved in the supplied source.
References
- Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar and David R. Wood, “Graphs of Linear Growth have Bounded Treewidth”, arXiv:2210.13720 (2022).
Progress summary
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.