Girth and treewidth

DOI10.1016/j.jctb.2004.05.004zbMath1064.05084OpenAlexW2081464744MaRDI QIDQ707020

C. R. Subramanian, L. Sunil Chandran

Publication date: 9 February 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2004.05.004

zbMATH Keywords

tree decompositionminorsaverage degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83)

Related Items (17)

Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Learning loopy graphical models with latent variables: efficient methods and guarantees ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width ⋮ Some bounds on the zero forcing number of a graph ⋮ Isoperimetric Problem and Meta-fibonacci Sequences ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ The forcing number of graphs with given girth ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Bounds on the connected forcing number of a graph ⋮ Treewidth computations. II. Lower bounds ⋮ Unnamed Item ⋮ A short proof for a lower bound on the zero forcing number ⋮ The carvingwidth of hypercubes ⋮ On the maximum cardinality search lower bound for treewidth ⋮ Bounds on isoperimetric values of trees ⋮ The descriptive complexity of subgraph isomorphism without numerics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dense minors in graphs of large girth
• Lower bound of the Hadwiger number of graphs by their average degree
• Girth in graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Topological subgraphs in graphs of large girth
• The Moore bound for irregular graphs
• Topological minors in graphs of large girth
• An extremal function for contractions of graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• A High Girth Graph Construction
• Minors in graphs of large girth
• Subdivisions of $K_{r+2}$ in Graphs of Average Degree at Least $r+\varepsilon$ and Large but Constant Girth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Girth and treewidth