Polynomial graph invariants from homomorphism numbers

DOI10.1016/J.DISC.2015.11.022zbMATH Open1329.05156arXiv1308.3999OpenAlexW1718505034MaRDI QIDQ906477FDOQ906477

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

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Chromatic invariants for finite graphs: Theme and polynomial variations
• Counting graph homomorphisms
• Upper bounds to the clique width of graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Title not available (Why is that?)
• Sparsity. Graphs, structures, and algorithms
• 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
• The enumeration of vertex induced subgraphs with respect to the number of components
• A Most General Edge Elimination Polynomial
• Title not available (Why is that?)
• On Counting Generalized Colorings

Cited In (11)

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

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)