A Most General Edge Elimination Polynomial

DOI10.1007/978-3-540-92248-3_4zbMath1202.05063arXiv0712.3112OpenAlexW1509099547MaRDI QIDQ5302041

Ilia Averbouch, Benny Godlin, Johann A. Makowsky

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

edge contractionedge deletionedge eliminationedge extraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31)

Related Items

On the Tutte and Matching Polynomials for Complete Graphs, In praise of homomorphisms, Harary polynomials, Polynomial graph invariants from homomorphism numbers, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Complexity and approximability of the cover polynomial, Weakly distinguishing graph polynomials on addable properties, The enumeration of vertex induced subgraphs with respect to the number of components, Bivariate chromatic polynomials in computer algebra, Acyclic polynomials of graphs, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, Tutte polynomials of vertex-weighted graphs and group cohomology, An extension of the bivariate chromatic polynomial, On the reconstruction of graph invariants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• An extension of the bivariate chromatic polynomial
• The vertex-cover polynomial of a graph
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• On graph invariants given by linear recurrence relations
• Upper bounds to the clique width of graphs
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Parametrized complexity theory.
• On the colored Tutte polynomial of a graph of bounded treewidth
• Theory of monomer-dimer systems
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• A Most General Edge Elimination Polynomial – Thickening of Edges
• A Tutte Polynomial for Coloured Graphs
• Graph-Theoretic Concepts in Computer Science