On the number of labeled graphs of bounded treewidth

DOI10.1007/978-3-319-68705-6_7zbMath1486.05292arXiv1604.07273OpenAlexW2963386661MaRDI QIDQ5915790

Julien Baste, Ignasi Sau, Marc Noy

Publication date: 4 January 2018

Published in: European Journal of Combinatorics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.07273

zbMATH Keywords

treewidthenumerationpathwidthpartial \(k\)-treesproper-pathwidthlabeled \(k\)-trees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Unnamed Item, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• An asymptotic analysis of labeled and unlabeled \(k\)-trees
• Kernelization using structural parameters on sparse graph classes
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Mixed searching and proper-path-width
• Graph minors. X: Obstructions to tree-decomposition
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Treewidth. Computations and approximations
• On random planar graphs, the number of planar graphs and their triangulations
• \(\Gamma \)-species and the enumeration of \(k\)-trees
• Counting unlabeled \(k\)-trees
• Enumeration and limit laws for series-parallel graphs
• Enumerating k-trees
• On the Number of Distinct Forests
• Subexponential Time Algorithms for Finding Small Tree and Path Decompositions
• Subexponential Time Algorithms for Embedding H-Minor Free Graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A Near-Optimal Planarization Algorithm
• Parameterized Algorithms
• The number of labeled k-dimensional trees
• The number of labeled k-trees