Counting \(H-\)colorings of partial \(k-\)trees
From MaRDI portal
Publication:1603695
DOI10.1016/S0304-3975(02)00017-8zbMath0996.68132MaRDI QIDQ1603695
Dimitrios M. Thilikos, Maria J. Serna, Josep Diaz
Publication date: 15 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Lower Bounds for the Graph Homomorphism Problem, Some complete and intermediate polynomials in algebraic complexity theory, Fixed-Parameter Tractability of Treewidth and Pathwidth, Counting Small Induced Subgraphs Satisfying Monotone Properties, Towards a dichotomy theorem for the counting constraint satisfaction problem, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Monotone arithmetic complexity of graph homomorphism polynomials, List homomorphism: beyond the known boundaries, Faster algorithms for finding and counting subgraphs, Counting models for 2SAT and 3SAT formulae, Unnamed Item, Parameterized counting of partially injective homomorphisms, Nonempty intersection of longest paths in series-parallel graphs, On list \(k\)-coloring convex bipartite graphs, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
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
