Characterisation of graphs of linear growth by tree blow-ups
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.
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.