A graph polynomial for independent sets of bipartite graphs

DOI10.1017/S0963548312000296zbMATH Open1247.05111OpenAlexW2122924340MaRDI QIDQ2911069FDOQ2911069

Authors: Q. Ge, D. Štefankovič 

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548312000296

Recommendations

• A graph polynomial for independent sets of bipartite graphs
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• On the Complexity of the Interlace Polynomial

zbMATH Keywords

matchingsgraph polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• A Contribution to the Theory of Chromatic Polynomials
• Title not available (Why is that?)
• Random generation of combinatorial structures from a uniform distribution
• The relative complexity of approximate counting problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Graph polynomials and their applications. I: The Tutte polynomial
• On the computational complexity of the Jones and Tutte polynomials
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Complexity of Ferromagnetic Ising with Local Fields
• The computational complexity of two‐state spin systems
• An approximation trichotomy for Boolean \#CSP
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of counting in sparse, regular, and planar graphs
• On Counting Independent Sets in Sparse Graphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• Computational complexity of counting problems on 3-regular planar graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph polynomials and their applications. II: Interrelations and interpretations
• A two-variable interlace polynomial
• On Markov Chains for Independent Sets
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• A two-variable Artin conjecture
• Prime divisors of the Lagarias sequence
• Dynamic Matrix Rank

Cited In (11)

• Random-cluster dynamics in \(\mathbb {Z}^2\)
• Mixing of Markov chains for independent sets on chordal graphs with bounded separators
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
• Bipartite graphs as polynomials and polynomials as bipartite graphs
• An algorithm for calculating the independence and vertex-cover polynomials of a graph
• On the independence polynomial of an antiregular graph
• A graph polynomial for independent sets of bipartite graphs
• Julia set of some graphs using independence polynomials
• A graph polynomial arising from community structure (extended abstract)
• A polynomial Turing-kernel for weighted independent set in bull-free graphs

This page was built for publication: A graph polynomial for independent sets of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911069)