Counting homomorphisms to sparse graphs

DOI10.1016/J.ENDM.2009.07.065MaRDI QIDQ2851494zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez

Publication date 10 October 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.07.065

zbMATH Keywords

Boolean querycountinggraphhomomorphismnowhere dense classtree-depth

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Sparsity. Graphs, structures, and algorithms
• Sparse combinatorial structures: classification and applications
• On the number of types in sparse graphs
• On nowhere dense graphs
• Extremal problems for sparse graphs

Cites work

• Colouring graphs with bounded generalized colouring number
• Counting graph homomorphisms
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Finite Model Theory on Tame Classes of Structures
• First order properties on nowhere dense structures
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Homomorphism preservation theorems
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• On nowhere dense graphs
• On the order of countable graphs
• Operations with structures
• Optimal node ranking of tree in linear time
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(6)

• Homomorphisms from sparse graphs with large girth.
• scientific article; zbMATH DE number 6691415 (Why is no real title available?)
• Sparse combinatorial structures: classification and applications
• On counting homomorphisms to directed acyclic graphs
• Counting Subgraphs via Homomorphisms
• Homomorphisms from sparse graphs to the Petersen graph

This page was built for publication: Counting homomorphisms to sparse graphs

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