Girth and treewidth (Q707020): Difference between revisions

Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \(\text{tw}(G)\) of a graph \(G\), giving a lower bound in terms of the girth \(g(G)\) and average degree \(d(G)\). They show that \[ \text{tw}(G)\geq c {1\over g(G)+1} (d(G)-1)^{\lfloor (g(G) -1)/2\rfloor} \] holds. Since the treewidth is smaller than the vertex number of the graph, \(\text{tw}(G) < v(G)\), and the existence of a graph with \[ v(G)\leq c^{\prime} (d(G)-1)^{\lfloor( g(G)-1 )/2\rfloor} \] is conjectured, this bound appears to be almost tight.