Filter

Glossary

What do the properties of a graph class $\mathcal{F}$ mean?

• characterised as characterisation of the homomorphism indistinguishability relation $\equiv_{\mathcal{F}}$
• complexity complexity of deciding whether two input graphs $G$ and $H$ are homomorphism indistinguishable over $\mathcal{F}$.
• homomorphism distinguishing closed $\mathcal{F}$ is homomorphism distinguishing closed if, for all $F \not\in \mathcal{F}$, there exist graphs $G$ and $H$ such that $G \equiv_{\mathcal{F}} H$ and $\hom(F, G) \neq \hom(F, H).$
• witness function a witness function for $\mathcal{F}$ is a function $f \colon \mathbb{N} \to \mathbb{N}$ such that for all graphs $G$ and $H$ on at most $n$ vertices, $G \equiv_{\mathcal{F}} H$ if, and only if, $G \equiv_{\mathcal{F}_{\leq f(n)}} H$ where $\mathcal{F}_{\leq N}$ is the class of the $F \in \mathcal{F}$ on at most $N$ vertices.

View

Toggle references

Download

Data is licensed under CC0 1.0 Universal. This page gratefully relies on data from Wikidata.

Download data Get in touch