Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants

DOI10.1007/978-3-540-69407-6_43MaRDI QIDQ3507454zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_43

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algebraic theory of graph reduction
• scientific article; zbMATH DE number 177426
• Uniform reducibility of representability problems for algebraic structures
• Algebraic graph invariants and reconstruction
• Polynomial graph invariants from homomorphism numbers
• Polynomial graph invariants from homomorphism numbers
• A unified construction of semiring-homomorphic graph invariants
• Inductive graph invariants and algorithmic applications
• On Numerical Invariant of Graph
• Reduction graph and its application on algebraic graphs

Cites work

• A Tutte Polynomial for Coloured Graphs
• A two-variable interlace polynomial
• A weighted graph polynomial from chromatic invariants of knots
• Complexity of the Bollobás-Riordan Polynomial
• Complexity of the Cover Polynomial
• Counting graph homomorphisms
• Edge coloring models and reflection positivity
• From a zoo to a zoology: Towards a general theory of graph polynomials
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• On the algebraic complexity of some families of coloured Tutte polynomials
• On the Complexity of the Interlace Polynomial
• On the computational complexity of the Jones and Tutte polynomials
• On the cover polynomial of a digraph
• On the Harmonious Coloring of Graphs
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The complexity of partition functions
• The interlace polynomial of a graph
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

Cited in

(1)

• My writing

This page was built for publication: Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants

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