Characterisation of graphs of linear growth by tree blow-ups

For a graph GG, write fG(r)f_G(r) for its growth function, and let GHG\boxtimes H denote the strong product of graphs GG and HH. Let KtK_t be the complete graph on tt vertices. A graph is said to have linear growth with parameter cc when fG(r)crf_G(r)\leqslant cr for c\ba1c\ba1.

Linear-growth product-structure conjecture. There exist functions g ⁣:RNg\colon\mathbb{R}\to\mathbb{N} and h ⁣:RRh\colon\mathbb{R}\to\mathbb{R} such that for any c1c\geqslant 1, every graph GG with growth fG(r)crf_G(r)\leqslant cr is isomorphic to a subgraph of

TKg(c)T\boxtimes K_{g(c)}

for some tree TT with growth fT(r)h(c)rf_T(r)\leqslant h(c)r.

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

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.