Characterisation of polynomial-growth graphs by products of trees
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.
Sources & referencesView supporting material
Primary source
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
Sign in to submit a solution.
No solutions have been posted yet.