Characterisation of graphs of linear growth by tree blow-ups
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 is said to have linear growth with parameter when for .
Linear-growth product-structure conjecture. There exist functions and such that for any , every graph with growth is isomorphic to a subgraph of
for some tree with growth .
If true, this would approximately characterise graphs of linear growth: every subgraph of such a product has linear growth, while the preceding theorem gives a product-structure result with a possibly exponentially growing tree. The conjecture remains 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.