Forbidden Induced Subgraphs for Bounded $p$-Intersection Number

A graph $G$ has $p$-intersection number at most $d$ if it is possible to assign to every vertex $u$ of $G$, a subset $S(u)$ of some ground set $U$ with $\mathrm{\mid }U\mathrm{\mid }=d$ in such a way that distinct vertices $u$ and $v$ of $G$ are adjacent in $G$ if and only if $\mathrm{\mid }S(u)\cap S(v)\mathrm{\mid }\ge p$. We show that every minimal forbidden induced subgraph for the hereditary class $\mathcal{G}(d,p)$ of graphs whose $p$-intersection number is at most $d$, has order at most $3\cdot 2^{d+1}+1$,andthattheexponentialdependenceon$d$ in this upper bound is necessary. For $p\in \{d-1,d-2\}$, we provide more explicit results characterizing the graphs in $\mathcal{G}(d,p)$ without isolated/universal vertices using forbidden induced subgraphs.