Strongly polynomial sequences as interpretations

DOI10.1016/j.jal.2016.06.001zbMath1436.05052arXiv1405.2449OpenAlexW2287806834MaRDI QIDQ334158

Patrice Ossona de Mendez, Jaroslav Nešetřil, Andrew J. Goodall

Publication date: 31 October 2016

Published in: Journal of Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

graph homomorphismrelational structuregraph polynomialinterpretation scheme

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Model theory of finite structures (03C13) Applications of model theory (03C98) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

In praise of homomorphisms ⋮ On sequences of polynomials arising from graph invariants ⋮ First-order limits, an analytical perspective ⋮ Regular partitions of gentle graphs ⋮ A logician's view of graph polynomials

Cites Work

• The enumeration of vertex induced subgraphs with respect to the number of components
• Polynomial graph invariants from homomorphism numbers
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Chromatic invariants for finite graphs: Theme and polynomial variations
• Regularity partitions and the topology of graphons
• Quasi‐carousel tournaments
• Acyclic colorings of planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item