Minimal normal graph covers (Q2416445)

A graph $G$ is called $(c,s)$ normal if there exists a collection $\mathcal{C}$ of cliques of $G$ with $\left\vert C\right\vert \leq c$ for each $C\in \mathcal{C}$ and a collection $\mathcal{S}$ of independent sets of $G$ with $\left\vert S\right\vert \leq s$ for each $S\in \mathcal{S}$ such that (i) both $\mathcal{C}$ and $\mathcal{S}$ form a vertex covering of $G$ and (ii) every clique in $\mathcal{C}$ and every independent set in $\mathcal{S}$ have a non-empty intersection. The main result of the paper states that the order of a $(c,s)$ normal graph is at most $2^{c+s}.$