Induced saturation number

In this paper, we discuss a generalization of the notion of saturation in graphs in order to deal with induced structures. In particular, we define indsat ( n , H ) , which is the fewest number of gray edges in a trigraph so that no realization of that trigraph has an induced copy of H , but changing any white or black edge to gray results in some realization that does have an induced copy of H . e some general and basic results and then prove that indsat ( n , P 4 ) = ⌈ ( n + 1 ) / 3 ⌉ for n ≥ 4 where P 4 is the path on 4 vertices. We also show how induced saturation in this setting extends to a natural notion of saturation in the context of general Boolean formulas.