Counting \(H-\)colorings of partial \(k-\)trees

DOI10.1016/S0304-3975(02)00017-8zbMath0996.68132MaRDI QIDQ1603695

Dimitrios M. Thilikos, Josep Diaz, Maria J. Serna

Publication date: 15 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

treewidth; graph homomorphism; counting problems

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Faster algorithms for finding and counting subgraphs, Towards a dichotomy theorem for the counting constraint satisfaction problem, Counting models for 2SAT and 3SAT formulae, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Fixed-Parameter Tractability of Treewidth and Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The core of a graph
• Graph minors. III. Planar tree-width
• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• The complexity of colouring problems on dense graphs
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Treewidth. Computations and approximations
• The complexity of \(H\)-colouring of bounded degree graphs
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• List homomorphisms and circular arc graphs
• On Markov Chains for Randomly H-Coloring a Graph
• Algorithms finding tree-decompositions of graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On Approximately Counting Colorings of Small Degree Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic