A unified construction of semiring-homomorphic graph invariants

Understand

It has recently been observed by Zuiddam that finite graphs form a preordered commutative semiring under the graph homomorphism preorder together with join and disjunctive product as addition and multiplication, respectively.

• This led to a new characterization of the Shannon capacity $\Theta$ via Strassen's Positivstellensatz: $\Theta(\bar{G}) = \inf_f f(G)$, where $f : \mathsf{Graph} \to \mathbb{R}_+$ ranges over all monotone semiring homomorphisms.
• Constructing and classifying graph invariants $\mathsf{Graph} \to \mathbb{R}_+$ which are monotone under graph homomorphisms, additive under join, and multiplicative under disjunctive product is therefore of major interest.
• We call such invariants semiring-homomorphic.