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 (V_1, V_2,…,V_k) such that, for each i, 1 ≤ 1 ≤ k, G[V_i], the subgraph of G induced by V_i, 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 K_2 or C_(4k+2) or the Petersen graph, where C_n is the cycle of length n.
展开▼
