Induced matching partition number

Induced matching partition number --- число разбиения индуцированного паросочетания.

The induced matching partition number of a graph [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ imp(G) }[/math], is the minimum integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ V(G) }[/math] has a [math]\displaystyle{ k }[/math]-partition [math]\displaystyle{ (V_{1}, \ldots, V_{k}) }[/math] such that, for each [math]\displaystyle{ i }[/math], [math]\displaystyle{ 1 \leq i \leq k }[/math], [math]\displaystyle{ G[V_{i}] }[/math], the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ V_{i} }[/math], is 1-regular graph. It is known that, if [math]\displaystyle{ G }[/math] is a graph which has a perfect matching, then [math]\displaystyle{ imp(G) \leq 2\Delta(G) - 1 }[/math], where [math]\displaystyle{ \Delta(G) }[/math] is the maximum degree of a vertex of [math]\displaystyle{ G }[/math]. Furthermore, [math]\displaystyle{ imp(G) = 2\Delta(G) - 1 }[/math] if and only if [math]\displaystyle{ G }[/math] is isomorphic to either [math]\displaystyle{ K_{2} }[/math] or [math]\displaystyle{ C_{4k+2} }[/math] or the Petersen graph, where [math]\displaystyle{ C_{n} }[/math] is the cycle of length [math]\displaystyle{ n }[/math].