Girth and treewidth (Q707020): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jctb.2004.05.004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2081464744 / rank | |||
Normal rank |
Revision as of 22:18, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Girth and treewidth |
scientific article |
Statements
Girth and treewidth (English)
0 references
9 February 2005
0 references
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.
0 references
average degree
0 references
tree decomposition
0 references
minors
0 references