A note on the computational complexity of weak saturation

Martin Tancer, Mykhaylo Tyomkyn

We prove that determining the weak saturation number of a host graph $F$ with respect to a pattern graph $H$ is already a computationally hard problem when $H$ is the triangle. As…