Girth and treewidth
From MaRDI portal
Publication:707020
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
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
