Affordable Access

Publisher Website

Counting Homomorphisms to Sparse Graphs

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
34
Identifiers
DOI: 10.1016/j.endm.2009.07.065
Keywords
  • Graph
  • Counting
  • Homomorphism
  • Boolean Query
  • Tree-Depth
  • Nowhere Dense Class
Disciplines
  • Mathematics

Abstract

Abstract We define nowhere dense and somewhere dense classes by means of counting of homomorphisms from test graphs. This seems to be bridging the gap between existential and counting theorems (for graph homomorphisms) and it has application to complexity of Boolean queries.

There are no comments yet on this publication. Be the first to share your thoughts.