Partition the vertices of a graph into induced matchings

The induced matching partition number of a graph G, denoted by imp(G), is the minimum integer k such that V(G) has a k-partition (V1,V2,…,Vk) such that, for each i, 1⩽i⩽k, G[Vi], the subgraph of G induced by Vi, is a 1-regular graph. This is different from the strong chromatic index—the minimum size of a partition of the edges of graph into induced matchings. It is easy to show, as we do in this paper, that, if G is a graph which has a perfect matching, then imp(G)⩽2Δ(G)−1, where Δ(G) is the maximum degree of a vertex of G. We further show in this paper that, when G is connected, imp(G)=2Δ(G)−1 if and only if G is isomorphic to either K2 or C4k+2 or the Petersen graph, where Cn is the cycle of length n.