Polynomial graph invariants from homomorphism numbers

DOI10.1016/J.DISC.2015.11.022MaRDI QIDQ906477zbMATH OpenOpenAlexFDO

Authors Delia Garijo, Andrew Goodall, J. Nešetřil

Publication date 21 January 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph polynomialgraph homomorphismgraph sequence

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We give a method of generating strongly polynomial sequences of graphs, i.e., sequences $(H_{mathbfk})$ indexed by a multivariate parameter $mathbfk=(k_1,ldots,k_h)$ such that, for each fixed graph $G$, there is a multivariate polynomial $p(G;x_1,ldots,x_h)$ such that the number of homomorphisms from $G$ to $H_{mathbfk}$ is given by the evaluation $p(G;k_1,ldots,k_h)$. A classical example is the sequence $(K_k)$ of complete graphs, for which $mhom(G,K_k)=P(G;k)$ is the evaluation of the chromatic polynomial at $k$. Our construction produces a large family of graph polynomials that includes the Tutte polynomial, the Averbouch-Godlin-Makowsky polynomial and the Tittmann-Averbouch-Makowsky polynomial. We also introduce a new graph parameter, the {em branching core size} of a simple graph, related to how many involutive automorphisms with fixed points it has. We prove that a countable family of graphs of bounded branching core size (which in particular implies bounded tree-depth) is always contained in a finite union of strongly polynomial sequences.

Recommendations

• Polynomial graph invariants from homomorphism numbers
• Homomorphisms and Polynomial Invariants of Graphs
• Homomorphisms and polynomial invariants of graphs
• Polynomial Invariants of Graphs
• Polynomial graph invariants and linear hierarchies
• scientific article; zbMATH DE number 4047782
• Polynomials and graph homomorphisms
• Graphs determined by polynomial invariants
• Polynomial invariants of graphs. II
• Polynomial graph invariants and the KP hierarchy

Cites work

• scientific article; zbMATH DE number 177438 (Why is no real title available?)
• scientific article; zbMATH DE number 2038883 (Why is no real title available?)
• A Most General Edge Elimination Polynomial
• Chromatic invariants for finite graphs: Theme and polynomial variations
• Counting graph homomorphisms
• Distinguishing graphs by their left and right homomorphism profiles
• From a zoo to a zoology: Towards a general theory of graph polynomials
• On Counting Generalized Colorings
• On counting generalized colorings
• Sparsity. Graphs, structures, and algorithms
• The enumeration of vertex induced subgraphs with respect to the number of components
• Tree-depth, subgraph coloring and homomorphism bounds
• Upper bounds to the clique width of graphs
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)

Cited in

(11)

• A polynomial invariant of graphs in 3-manifolds
• In praise of homomorphisms
• Graphs determined by polynomial invariants
• Polynomials counting nowhere-zero chains in graphs
• Homomorphisms and polynomial invariants of graphs
• Polynomial graph invariants and linear hierarchies
• Strongly polynomial sequences as interpretations
• The expansion of polynomial invariants for $2$-decompositions of generalized graphs
• Polynomial graph invariants from homomorphism numbers
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• How I got to like graph polynomials

This page was built for publication: Polynomial graph invariants from homomorphism numbers

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