An extension of the bivariate chromatic polynomial

DOI10.1016/j.ejc.2009.05.006zbMath1198.05099OpenAlexW1968703234MaRDI QIDQ1041177

Benny Godlin, Ilia Averbouch, Johann A. Makowsky

Publication date: 1 December 2009

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2009.05.006

Mathematics Subject Classification ID

Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the roots of domination polynomial of graphs, On the Tutte and Matching Polynomials for Complete Graphs, Homotopy type of the Boolean complex of a Coxeter system., The average domination polynomial of graphs is unimodal, Harary polynomials, A Most General Edge Elimination Polynomial, On the number of perfect matchings of generalized theta graphs and the edge cover polynomials of friendship graphs, Note on the subgraph component polynomial, Bivariate order polynomials, Gallai-Edmonds structure theorem for weighted matching polynomial, Weakly distinguishing graph polynomials on addable properties, The enumeration of vertex induced subgraphs with respect to the number of components, Distinguishing graphs by their left and right homomorphism profiles, On the roots of edge cover polynomials of graphs, A bivariate chromatic polynomial for signed graphs, Acyclic polynomials of graphs, Unnamed Item, A logician's view of graph polynomials, On P-unique hypergraphs, On the location of roots of graph polynomials, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Contractors for flows

Cites Work

• Algorithmic uses of the Feferman-Vaught theorem
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Evaluating a weighted graph polynomial for graphs of bounded tree-width
• Matching theory
• A weighted graph polynomial from chromatic invariants of knots
• Chromatic polynomials of homeomorphism classes of graphs
• Chain polynomials and Tutte polynomials
• 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
• Complexity of the Bollobás-Riordan Polynomial
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• A Most General Edge Elimination Polynomial – Thickening of Edges
• Strong Tutte Functions of Matroids and Graphs
• A Tutte Polynomial for Coloured Graphs
• On the computational complexity of the Jones and Tutte polynomials
• On the Complexity of the Interlace Polynomial
• A Most General Edge Elimination Polynomial
• Complexity of the Cover Polynomial
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item